适用情境

滑动窗口最值

思路

维护一个区间内的部分元素下标所构成的单调序列，保证队头元素是最大（最小）的。

实现

239. 滑动窗口最大值 - 力扣（LeetCode）

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        //对于一个双端队列，可以在队头和队尾分别插入和删除元素
        vector<int> ans;
        int n = nums.size();
        for(int i = 0;i<n;i++){
        //下标可以从0开始，也可以从1开始（后面改成i>=k）
            while(!dq.empty() && nums[dq.back()] <= nums[i]){
                //翻译一下就是队尾元素不大于当前元素
                dq.pop_back();
            }
            dq.push_back(i);//把当前元素插入队尾
            if(i - dq.front() >= k){
                dq.pop_front();//删掉多余的元素
            }
            if(i >= k - 1){
                ans.push_back(nums[dq.front()]);//把队头元素添加到答案
            }
        }
        return ans;
    }
};