单调队列、栈

发表于2021-08-26更新于2021-08-27阅读次数

区间！最近！最值！

单调队列 单调栈 尺取法

Mmmm

1单调栈和单调队列一般用来求最近小，求最远小不能直接求，得结合二分
2单调队列和单调栈区别不大，或者说单调队列是包含单调栈的，其主要区别在于，单调队列可以在队头进行操作，即可以在一段区间的左边界进行相应操作，而单调栈不行。即对于一段子区间来说，单调栈只能变化子区间的右边界，而单调队列可以变化左右边界。
3 单调队列维护的区间范围是【队头，当前元素】，也就是说单调队列只能控制当前元素到左边的范围。如果题目要求控制当前元素两端的范围，比如-D<=x<=D，那么就得跑两遍单调队列，从左到右跑一遍，再从右到左跑一遍。

单调队列

1单调队列主要用于解决左端点可移动的区间最值问题。

经典例题，固定区间长度

题目链接 https://vjudge.net/problem/POJ-2823
题意：给一个固定长度的滑动窗口，输出窗口内的最大值和最小值
思路：跑单调队列即可
核心代码

1
2
3
4
5
6
7
8
for(int i=0;i<n;i++){
        while(!dq1.empty() && i-dq1.front().x+1>k)  dq1.pop_front();
        //维护区间左端点
        while(!dq1.empty() && a[i].n<dq1.back().n)  dq1.pop_back();
        //维护区间右端点
        dq1.push_back(a[i]);
        if(i-k>=-1)  printf("%d ",dq1.front());           
    }

经典例题，区间长度变化–结合尺取

题目链接 https://vjudge.net/problem/HDU-3530
题意：找一段最长连续子序列，其最大值减最小值的差满足差>=m且<=k
**思路**：与固定区间长度不同的是，此区间长度是变化的，故需要结合尺取法。需注意尺取法求区间和只能判断一个边界，而此题有两个边界，要求m<=区间和<=k,所以我们只取边界k，把>=m作为条件，以k为边界，在满足区间和<k的情况下，再判断是否满足>m即可。
核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(r=0;r<n;r++){
    DqmaxPushB(a[r]);
    DqminPushB(a[r]);
    length++;
    d=dqmax.front().n-dqmin.front().n;
    while(d>k){
        if(!dqmax.empty() && a[l].x==dqmax.front().x)  dqmax.pop_front();
        if(!dqmin.empty() && a[l].x==dqmin.front().x)  dqmin.pop_front();
        l++;
        length--;
        if(dqmax.empty() || dqmin.empty()){
            d=0;break;
        }  
        else  d=dqmax.front().n-dqmin.front().n;
    }
    if(d>=m)  if(length>maxl)  maxl=length;
}

灵活运用

题目链接 https://www.luogu.com.cn/problem/P3088
题意 如果在x左右为d的范围内，有>=2x的数，那么我们称x为拥挤的，求一数列中拥挤的x的数量。
思路 乍一看，求2x作为最大值对应的区间？好像跑个单调栈就出来了，但一上手发现不行，因为他要求的是两倍x，而我们单调栈中对应的是每个原数x，不是2*x，所以用单调栈不行。这道题是有两个区间，-d和d，但单调队列只能维护一边的区间，所以我们跑两次单调队列就可以了，从左到右一次，再从右到左一次。

灵活运用，求最远小

题目链接 https://vjudge.net/problem/CodeForces-91B
题意 一个数列，求每个数之前的最远的那个小于它的数与它之间有多少数，若无则输出-1.
思路 一般单调栈用来处理最近小，这个是最远小，但不过没关系，我们还是可以维护一个单调递减栈，对于每个元素，①如果其>=栈顶，则不入栈，因为小于它的数，肯定在前面；②如果其<栈顶，则入栈，输出-1

灵活运用，结合循环右移-倍增

题目链接 https://vjudge.net/problem/HDU-4193
题意 给一个长度为n的数列，循环右移k次，1<=k<=n-1，问有多少次右移的所有前i项和>=0。
思路 这题自己想的，结合自己整理的这篇文章，理清脉络，并不难想。真想夸自己聪明，毕竟这是隔了很久才自己做出来一道有挑战性的题目了，平常都是看题解，终于自己也聪明了一回 所有前i项和>=0嘛，转化下，常用数学思想，就是最小值>=0。循环右移k次，可以用倍增法，即倍增数组，也就转化为在2n长度的数组上，求固定长度为n的区间的最小值>=0的区间有多少个。数据处理方面，可以2n的数组为前缀和，最小值再减去区间前n项和就是当前区间最小值了。就是裸的固定长度单调队列了。

单调栈

经典例题，求最值及其对应区间

题目链接 https://vjudge.net/problem/POJ-2796
题意：求子序列之和乘以子序列的最小值的最大值
思路：单调栈经典题型，枚举n个最小值，以及其对应区间和。单调栈具体的实现就是弹栈时，其对应的栈中上下两个值即为边界。代码处理细节，加个栈底值和栈顶值，保证所有值都有左右边界，且都出栈。
核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for(ll i=0;i<=n+1;i++){
    while(!st.empty() && ar[i].n<=st.top().n){
        t=st.top().n;
        st.pop();
        l=st.top().x;
        r=ar[i].x;
        sum=Sum[r-1]-Sum[l];
        //cout<<r<<" "<<l<<endl;
        //cout<<sum<<" "<<t<<endl;
        mul=sum*t;
        if(mul>=maxmul){
            maxmul=mul;
            minl=l;
            maxr=r;
        }
    }
    st.push(ar[i]);
}

灵活运用

题目链接 https://blog.csdn.net/zuzhiang/article/details/78136417
题意 求仅由0，1组成的矩阵中，全部由1组成的子矩阵的最大面积。
思路 这道题需要先预处理下数据，因为它是全部由1组成的矩阵，所以需要连续的1，故我们把连续的1转换成长度表示最好，这样子就十分直观。剩下的就是以每行为底，求以每列为宽对应的区间即可，即转化为求最小值及对应区间问题。

灵活运用，维护最小值单调栈

题目链接 https://darkbzoj.tk/problem/1113
题意 许多个高度不等的矩形排列在一起，问最少用多少个矩形可以将其全部覆盖
思路 什么时候能少用一个矩形呢，那就是当在这个矩形之前，有个高度跟他一样的矩形，且这两个矩形之间的高度都要高于他才可以。故维护一个最小值单调栈即可
核心代码

1
2
3
4
5
6
7
for(int i=0;i<n;i++){
    while(!st.empty() && st.top()>h){
        st.pop();
    }
    if(!st.empty() && st.top()==h)  ans--;
    st.push(h);
}