力扣 -- 滑动窗口

定长的窗口

239. 滑动窗口最大值

239. 滑动窗口最大值
给定一定长度为 $k$ 的窗口，从数组的最左侧移动到到数组最右侧，每次移动一位，移动过程中纪录窗口中最大值。

难点：移动的过程中，如何纪录窗口内的最大值。
我们可以使用双端队列 / 单调队列创建一个窗口，其里面的元素是索引而不是数组的元素；在移动的过程中我们不断维护队列的单调性，即队列中下标对应的数组元素是单调递增的。此外，若要保持窗口的大小为 $k$ 的话，则当前下标 $i$ 与队头数值 $j$ 需要不等式 $i-j<k$ 成立。
若上述的条件满足，则队列中的数值对应的数组元素就是当前窗口的最大值。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n, ans = len(nums), []
        deque = collections.deque()
        for j in range(n):
            while len(deque) != 0 and nums[j] >= nums[deque[-1]]:
                deque.pop() # 如果新来的元素大于队尾元素，则删除队尾元素
            deque.append(j)
            if j - deque[0] >= k:  # 非窗口内的元素
                deque.popleft()
            if j >= k - 1: 
                ans.append(nums[deque[0]])
        return ans

不定长的窗口

862. 和至少为 K 的最短子数组

862. 和至少为 K 的最短子数组
给定一个整数数组 nums 和一个整数 $k$，需要找到和至少为 $k$ 的最短子数组的长度。如果没有这样的子数组，则返回 -1。

难点：数组的范围为 $[-10^5,10^5]$，即数组可能包含负数，不能简单地移动左指针来收缩窗口，否则会错过满足条件的较短子数组，因此双指针的窗口不适用。

在这种情况下，我们可以使用单调队列和前缀和数组，它能动态地保持一个符合条件的窗口并确保子数组长度尽可能短。

• 为了快速求得子数组的和，我们使用前缀和数组 $s$ 来求得数组的 $[i:j]$ 这个区域内的和，即 $\text{sum}(nums[i:j])=\text{s}[j]-\text{s}[i]$。此时若这个 $\text{sum}(nums[i:j])=s[j]-s[i]\ge k$，则表示区间 $[i:j]$ 是一个满足条件的子数组。
• 为了找到最短子数组的长度，我们使用一个双端队列 deque 存储前缀和数组的索引，维护 deque 单调递增，即队列中的索引对应的前缀和元素在队列中是单调递增的。
  队头条件的检查：当遍历到索引 $j$ 时， 检查队头索引 $i$ 是否存在满足 $s[j]-s[i]>=k$，若满足则更新答案，并将队头索引出队。额外的，我们还要继续检查 $[i+1:j]$ 是否满足以上的条件（得到更短的长度）。
  保持单调性：遍历到索引 $j$ 时，移除队尾所有满足 $s[j]\le s[q[-1]]$ 的索引。因为存在队尾元素 $i$，当 $s[i]\ge s[j]$ 时，$s[i]$ 不再有用，因为 $s[j]$ 更小且出现在更右侧，未来更有可能形成更短的子数组（存在未来的元素 $x$ 且 $x\ge s[i]$，若 $x-s[i]\ge k$，则 $x-[j]\ge k$ 成立，则从 $j$ 开始的范围更小）。

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        s = list(accumulate(nums, initial=0))  # 前缀和数组，从 0 开始
        ans, q = inf, deque()
        for i, curS in enumerate(s):
            while q and curS-s[q[0]] >= k:
                ans = min(ans, i-q.popleft())
            while q and s[q[-1]] >= curS:
                q.pop()
            q.append(i)
        return ans if ans < inf else -1