滑动窗口的最大值问题解析与代码实现

滑动窗口最大值问题是一种常见的算法问题，通常出现在处理数组或列表时。给定一个数组和一个大小为k的滑动窗口，我们需要从左到右滑动这个窗口，并找到每个窗口内的最大值。

例如，给定数组 [1,2,7,7,8] 和滑动窗口大小 k = 3，我们需要找到每个长度为3的窗口的最大值，结果为 [7,7,8]。

解决这个问题的一种有效方法是使用双端队列。双端队列是一个特殊的队列，允许我们在两端添加或删除元素。在这个问题中，我们可以使用双端队列来存储当前窗口中的元素下标，并保持队列中的元素下标是严格递减的。这样，队列的头部始终对应于当前窗口中的最大值。

以下是一个Python代码实现：

def maxSlidingWindow(nums, k):
    if len(nums) < k or not nums:
        return []
    result = []
    qmax = []  # 双端队列，存储元素下标
    for i in range(len(nums) - k + 1):
        # 如果当前元素在队列中，移除它
        if qmax and qmax[0] == i - k:
            qmax.pop(0)
        # 保持队列严格递减
        while qmax and nums[qmax[-1]] < nums[i]:
            qmax.pop()
        qmax.append(i)
        # 如果当前窗口已经形成，记录最大值
        if i + 1 == len(nums) - k + 1:
            result.append(nums[qmax[0]])
    return result

这段代码首先检查输入数组的长度是否小于滑动窗口的大小k，如果是，则直接返回空列表。然后初始化结果列表和双端队列qmax。接下来，对于数组中的每个位置i，代码执行以下操作：

• 如果当前元素在队列中，说明它已经滑出了当前窗口，因此需要将其从队列中移除。
• 保持队列严格递减。如果队列的头部元素小于当前元素，就将它从队列中移除，直到队列的头部元素大于或等于当前元素为止。
• 将当前元素的下标添加到队列中。
• 如果当前窗口已经形成（即i + 1等于数组长度减去k），则将队列头部的元素（即当前窗口的最大值）添加到结果列表中。
• 最后返回结果列表。

这个算法的时间复杂度是O(n)，其中n是数组的长度，因为我们需要遍历每个元素一次。空间复杂度是O(k)，因为我们需要使用双端队列来存储每个窗口的元素下标。