239. 滑动窗口最大值

239. 滑动窗口最大值

#队列#单调队列 2025-01-21

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> head_max; // 下标
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (head_max.empty()) {
                head_max.push_back(i);
            } else {
                int distance = head_max.back() - head_max.front(); // 前后两个元素距离
                if (distance + 1 == k) {                // 距离超过 k ，弹出左边第一个元素
                    head_max.pop_front();
                }
                while (!head_max.empty() && nums[i] > nums[head_max.back()]) {  // 更新，保证单调递减
                    head_max.pop_back();
                }
                head_max.push_back(i);
            }
            if (i >= k - 1) {   // 只有下标 开始进入到统计范围，才开始加入到返回结果中
                result.push_back(nums[head_max.front()]);
            }
        }
        return result;
    }
};

这道题要考虑的问题很多，要时刻注意窗口的滑动，导致某些下标对应的元素已经不在统计范围内，要在恰当时刻移除。

1. 什么时候弹出左边的第一个元素？

deque 中存储的不是元素，而是下标，这样可以方便计算第一个元素和最后一个元素之间的距离。如果距离 + 1 等于 k，就该弹出左边的第一个元素，因为如上图所示，随着飞机的移动，左边的数据将可能不在统计范围（飞机考虑的视野）内。

你可能有个疑问，可不可以不通过距离，而是通过 deque 中存在的元素个数来判断？不可以！因为后面会看到，为了保证单调性，中间某些元素会被移除，这就会导致明明已经超过统计范围，却不自知。

2. 如何保证元素弹出依旧能够维持单调性？

首先我得保证 deque 中有至少一个元素，否则也无需关心单调性。

基于这个前提讨论，本题要保证单调递减。让即将添加的元素和队列中最后一个元素进行比较，如果大于即将添加的元素大于队列中最后一个元素，就得把队列中最后一个元素弹出。继续进行这种比较，直到小于队列中最后一个元素或者队列为空为止。

3. 为什么选择双端队列？

因为要从后面弹出元素，队列 queue 做不到。