题目：给定数组 nums 和窗口大小 k，返回每个窗口内的最大值。 暴力做法对每个窗口扫描 k 个元素，O(nk)。当 n、k 都很大时，需要 O(n) 的在线算法。

核心想法

用双端队列 deque 存储下标（不是值），并保持对应值单调递减：

  • 队头下标对应当前窗口最大值；
  • 队尾到队头，nums 值严格递减；
  • 新元素 nums[i] 入队前，从队尾弹出所有值 ≤ nums[i] 的下标——它们不可能再成为未来窗口的最大值。

窗口滑动

当 i ≥ k - 1 时，窗口为 [i - k + 1, i]：

  1. 若队头下标已滑出窗口左边界（< i - k + 1），从队头弹出；
  2. 队头下标即为当前窗口最大值，记入答案。

均摊 O(1) 的直觉

每个下标最多入队一次、出队一次，总共 O(n) 次双端队列操作，故整体 O(n)。 这是典型的「摊还分析」——单次看起来可能弹多个元素，但全局长度有限。

C++ 示意

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;  // indices
    vector<int> ans;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k)
            dq.pop_front();
        if (i >= k - 1)
            ans.push_back(nums[dq.front()]);
    }
    return ans;
}
求窗口最小值时，把比较方向反过来，维护单调递增队列即可。LeetCode 239、剑指 Offer 59-II 都是同一套路。