单调队列

分析

滑动窗口并不对应单调队列

滑动窗口问题可以用双指针 和 队列 两种方式实现

单调队列只是针对这个窗口里的某个性质 将不必要的元素舍去

从而能在O(1)的时间内找到这个最值

一般也就两个场景

找窗口的最小值

void get_min(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k)
            hh++;
        //求最小 递增区间 若出现向下 出队
        while(hh<=tt && a[i]<=a[q[tt]])
            tt--;
        q[++tt]=i;
        //当前区间的最大值为队头
        b[i] = a[q[hh]];
    }
}

找窗口的最大值

void get_max(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k)
            hh++;
        //求最大 递减区间 若出现向上 出队
        while(hh<=tt && a[i]>=a[q[tt]])
            tt--;
        q[++tt]=i;
        //当前区间的最大值为队头
        b[i] = a[q[hh]];
    }
}

另外注意分析 我们要的答案是在插入新元素之前还是在插入新元素之后

void get_max/* min */(int a[],int b[],int tot,int k)
{
    int hh=0,tt=-1;
    for(int i=0;i<tot;i++)
    {
        if(hh<=tt && i-q[hh]>=k) //这里一定有等于 因为要腾空间放新元素 满了就得出去
            hh++;

        //具体操作也可能放在这里
        //这是把新元素放进去之前就找答案

        //最大最小只要改这里 最大应该是递减 最小应该是递增 出现异常就出队
        //另外注意代入情景看等于是否影响结果 一般是也剔除 除非是要什么最左边的 才考虑去=
        while(hh<=tt && a[i]>/* < */=a[q[tt]])
            tt--;
        q[++tt]=i;

        //具体操作可能放在这里
        //这是把新元素放进去后再找答案
    }
}

stl版

class Solution {
public:
    vector<int> maxInWindows/* minInWindows */(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for(int i=0;i<nums.size();i++)
        {
            if(!q.empty() && i-q.front()>=k)
                q.pop_front();

            //具体操作 情况2
            //……

            while(!q.empty() && nums[i]>= /* <= */ nums[q.back()])
                q.pop_back();
            q.push_back(i);

            //具体操作 情况1
            //……
            if(i>=k-1)
                res.push_back(nums[q.front()]);
        }
        return res;
    }
};

题目

更多题目：

⬅️ 直方图中最大的矩形 🏠 00-刷题理模型 ➡️ 切蛋糕