题目

给定一个数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。滑动窗口每次只向右移动一位，你只可以看到在滑动窗口内的k个数字，请返回滑动窗口中的最大值。

示例：

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

暴力法

暴力法，属于直观但效率较低的解法。它通过直接遍历每个可能的窗口，对每个窗口执行一次遍历来找到最大值。具体来说，对于数组中的每个位置 i，只要 i + k - 1 不超过数组长度，那就从 i 开始，向后取出 k 个元素，然后在这 k 个元素中找出最大值。使用暴力法求解本题的主要步骤如下。

1、外层循环。遍历数组，以每个位置作为滑动窗口的起始点。

2、内层循环。对于每个起始点，检查接下来的 k - 1 个元素，确定这个窗口内的最大值，并将每个窗口的最大值记录下来。

3、返回结果。最后，返回记录下来的每个窗口的最大值组成的数组。

根据上面的算法步骤，我们可以得出下面的示例代码。

def sliding_window_max_value_brute_force(nums, k):
    if not nums or k <= 0 or len(nums) < k:
        return []
    
    n = len(nums)
    res = []
    for i in range(n - k + 1):
        window_max = nums[i]
        for j in range(i + 1, i + k):
            window_max = max(window_max, nums[j])
        res.append(window_max)
    
    return res

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
# 输出：[3, 3, 5, 5, 6, 7]
print(sliding_window_max_value_brute_force(nums, k))

双端队列法

双端队列法利用了双端队列deque的特性，即可以在两端高效地进行插入和删除操作。通过双端队列，我们动态维护了一个可能包含最大值的索引集合，这个集合保证了队首元素所对应的数组元素始终是当前窗口的最大值。使用双端队列法求解本题的主要步骤如下。

1、初始化。遍历数组的前 k 个元素，构建初始窗口。同时，维护一个单调递减的双端队列，队列中存储的是数组元素的索引。队列中的索引对应的元素从队首到队尾是递减的，队首索引指向当前窗口的最大值。

2、移动滑动窗口。从第 k+1 个元素开始，每次向右移动窗口时，首先检查队首的索引是否已经不在窗口范围内。如果是，则将其从队列中移除。接着，将新加入窗口的元素索引与队列中的元素进行比较。如果新元素大于队列尾部的元素，那么将队列尾部的元素移除，直到新元素不大于队列中的任何元素为止，然后将新元素的索引加入队列。

3、收集结果。每次移动窗口后，队首的索引所对应的数组元素即为当前窗口的最大值，将其收集到结果数组中即可。

根据上面的算法步骤，我们可以得出下面的示例代码。

from collections import deque

def sliding_window_max_value_deque(nums, k):
    if not nums or k <= 0:
        return []
    
    deq = deque()
    max_values = []
    
    # 构建初始窗口
    for i in range(k):
        while deq and nums[i] >= nums[deq[-1]]:
            # 保持队列单调递减
            deq.pop()
        deq.append(i)
    
    # 添加第一个窗口的最大值
    max_values.append(nums[deq[0]])
    
    # 滑动窗口
    for i in range(k, len(nums)):
        # 移除不在窗口内的索引
        while deq and deq[0] <= i - k:
            deq.popleft()
        
        # 维护队列的单调性
        while deq and nums[i] >= nums[deq[-1]]:
            deq.pop()
        
        deq.append(i)
        max_values.append(nums[deq[0]])
    
    return max_values

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
# 输出：[3, 3, 5, 5, 6, 7]
print(sliding_window_max_value_deque(nums, k))

使用双端队列法求解本题时，需要特别注意以下几点。

1、单调性维护。双端队列中存储的是可能的最大值的索引，而不是值本身，这有助于我们快速定位并移除过期索引。

2、边界处理。确保在窗口移动时，正确处理队列中不在当前窗口范围内的索引。

总结

暴力法的时间复杂度为O(n * k)，其中n是数组长度，k是滑动窗口大小。因为对于数组中的每个元素，都需要检查一个大小为k的窗口，这在k较大或n很大时会导致性能问题。其空间复杂度为O(1)，除了存储结果的数组外，没有使用额外的空间。

双端队列法的时间复杂度为O(n)，n的含义同上。虽然每次窗口移动都可能遍历整个队列，但每个元素最多入队和出队各一次，故总的操作次数是线性的。其空间复杂度为O(k)，因为在任何时候，双端队列中最多存储k个索引。

可以看到，通过双端队列法，我们不仅解决了滑动窗口最大值问题，还利用特定数据结构特性优化了算法效率。