算法笔记之数组分割

不知道这种算法思想叫啥，暂时这么叫吧。一般是滑动窗口中使用，将数组分割成一个一个块，每个块单独考虑。

LeetCode 239. 滑动窗口最大值

问题描述：给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

要求，返回滑动窗口中的最大值。希望在线性时间复杂度解决问题。

示例输入：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

解题思路：将数组分割成k个一组的块，这样除了最后一组都是k个。每个窗口最多只分布在2个块中，这样只要计算出窗口在每个块中的最大值，再求两者的最大值，就是窗口的最大值。

这样我们借助两个数组left和right，长度和nums数组相同，left记录每个块中从左侧到当前元素的最大元素，right记录每个块中从右侧到当前元素的最大元素，这样right[i]和left[i + k - 1]就是窗口起点为i的时候左侧和右侧块中的最大值（当然二者有可能在一个块，这时二者大小相同，不影响逻辑），求出他们的最大值即可。

Python代码：

def maxSlidingWindow(self, nums, k):
    # 分块
    n = (len(nums) - 1) // k + 1
    left = []
    # 每个块从左到右计算最大值
    for i in range(n):
        max_value = -float('inf')
        if i != n - 1:
            for j in range(i * k, (i + 1) * k):
                if nums[j] > max_value:
                    max_value = nums[j]
                left.append(max_value)
        else:
            for j in range(i * k, len(nums)):
                if nums[j] > max_value:
                    max_value = nums[j]
                left.append(max_value)
    
    # 每个块从右到左计算最大值
    right = [0 for _ in range(len(nums))]
    for i in range(n):
        max_value = -float('inf')
        if i != n - 1:
            for j in range((i + 1) * k - 1, i * k - 1,  -1):
                if nums[j] > max_value:
                    max_value = nums[j]
                right[j] = max_value
        else:
            for j in range(len(nums) - 1, i * k - 1, -1):
                if nums[j] > max_value:
                    max_value = nums[j]
                right[j] = max_value

    # 计算每个窗口最大值
    result = []
    for i in range(len(nums) - k + 1):
        result.append(max(right[i], left[i + k - 1]))
    return result