Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

数据结构——单调栈

2022/03/08 数据结构
Word count: 4,879 | Reading time: 23min

秋季PAT的第一题就是单调栈,之前没怎么学过, 因此这次专门学习做下笔记。

单调栈Monotone Stack

概念:

从行为上看,它不仅仅是用存储与访问受限的栈,而是一种辅助工具,用于检测数据的单调性变化并作出反应(表现: 当入栈元素会影响栈总体单调性时,要出栈一些元素以维持单调性)

场景:

  • 向左or向右找到第一个稍大(小)的元素、其索引下标;
  • 确定某条件(单调)下的最长区间
  • 确定区间构成的极值,如max f(la,b]);

Point:

单调递增栈: 指栈内元素的出栈序列递增(或递减),而栈内元素是递减(或递增),即当元素比栈顶小的时候入栈。因此需要输出下一个最大的元素。

当然也有人是直接根据栈内元素大小关系来区别, 比如栈内元素递减就叫做递减栈。

此外没有双向栈的存在。

==>2021年10月26日——明确下定义:单调递减栈为出从栈底往栈顶看,元素大小成递减排列。其实上,正确的理解应该从扫描的角度来看,比如从左往右扫描时,如果元素依次递减,则统统会入栈,e.g. [4,2,1,5,8], ==> 当5入栈时,单调递减的栈[4,2,1]横过来看就是原列表单调递减的子序列。

归纳:

  • 当从左往右扫描维护单调递减栈时,可以求元素左边第一个比他大的元素,也可以求右边第一个比它大的元素
    • 左边第一个比他大的元素:当以入栈元素的角度看时,如果栈内元素一直比它小,则不断pop,直到pop不出去元素,那么剩下的栈顶元素就是左边第一个比它大的元素
    • 右边第一个比它大的元素:当以栈内元素的角度看时,把他pop出去的入栈元素就是当前栈顶元素右边第一个比它大的元素

可见:从不同的角度看,能得到不同的效果,代码编写的区别在于ans数组的更新:一个在while不断pop的过程中更新(栈内被弹走元素的角度),另一个是while到pop停下后更新(入栈元素的角度)。

实际上,左边第一个大的元素和右边第一个大的元素是等价的,因为当从左往右扫描时求右边第一个大的元素问题,当吧原序列翻转(或是从右往左扫描时),得到的结果就是对原序列而言每个数左边第一个大的元素。

核心思想

在元素Y入栈的时候会跟栈顶元素X比较, 如果Y比栈内所有元素Xs都大的话,就可以拿到栈里所有的元素即区间。关键是这个比较, 就可以找到第一个满足要求的数据。

e.g.有列表[1, 3, 2, 0, 7],从左向右遍历,当遍历为7时栈里有[3, 2, 0],此时入栈元素为7, 能得到==>那么对于0来说,右边最大的就是当前入栈元素7, 左边最小的就是栈内下一个元素2。而对3来说,此时3上边的元素就都是比3小的元素们。

Code模板:

1
2
3
4
5
6
7
8
9
def getFirstMax(nums: List[int]):
# 站内元素递减栈, 输出序列递增
stack = []
for i in range(len(nums) - 1, -1, -1):
val = nums[i]
if stack and val > stack[-1]:
stack.pop()
# 入栈操作在之前逻辑都执行完之哦吼,最后再入栈
stack.append(val)

这种写法, 主要是运用的stack.pop元素

例题

Leetcode#496:

单调栈

Leetcode #496. 下一个更大元素 I

1
2
3
4
5
6
7
8
9
10
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
hash_dict = dict()
stack = []
for i in nums2:
while stack and i > stack[-1]:
# 在原有序列中比栈顶元素大的就是当前入栈元素i
hash_dict[stack.pop()] = i
stack.append(i)
return [hash_dict.get(i,-1) for i in nums1]

Leetcode#962. 最大宽度坡

单调栈

Q: 为什么想到了单调栈?

A:参看题解:首先把A数组中的以A[0]开头的递减序列抽取出来,我们最后要求的最大的宽度坡一定是以这个序列中的某一个i为坡底的,我们反证一下

假设存在某个元素位置k不存在于上面的递减序列中,且有最大宽度j-k,这也就说明k位置的元素一定是小于k前面所有的元素的,否则就会有更长的宽度,但是既然k小于前面所有的元素,那么k就一定会被加入到序列中,与假设矛盾,所以不存在k,解一定存在递减序列中

这样的话我们可以逆向遍历数组,每次遇到元素大于栈顶的就可以计算宽度,然后将栈顶弹出,因为是逆序遍历的,所以这个宽度一定是栈顶这个坡底i能形成的最大宽度了, 逆序遍历再往前的话即使大于这个栈顶,形成的宽度也只会减小,所以这个栈顶是可以直接pop出去的,我们遍历所有的坡底求最大值就行了,时间复杂度O(N)

作者:resolmi https://leetcode-cn.com/problems/maximum-width-ramp/solution/java-dan-diao-zhan-er-fen-jie-fa-chang-shi-jie-shi/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
* @Author: Mrli
* @Date: 2020-09-14 10:16:57
* @LastEditTime: 2020-09-14 11:03:29
* @Description:
*/
#include <bits/stdc++.h>
using namespace std;

int maxWidthRamp(vector<int>& A) {
stack< int > st;
int len = A.size();
// 维护一个递减栈
for (int i = 0; i < len; i++) {
if (st.empty() || A[i] <= A[st.top()]) st.push(i);
}

int ans = 0;
int i = len - 1;
while( i > ans){
// 根据单调栈的含义, 此时入栈A[i], 可以得到 st.top() 右边比其大的为A[i], 同时栈里也都是比A[i]小的元素
while( !st.empty() && A[st.top()] <= A[i] ){
// printf("A[%d]:%d A[%d]:%d\n", st.top(), A[st.top()], i, A[i] );
ans = max(ans, i - st.top());
st.pop();
}
i --;
}
return ans;
}

int main(){
vector<int> A = {6,0,8,2,1,5};
int ans = maxWidthRamp(A);
cout <<ans <<endl;
return 0;
}

Leetcode#1124:

前缀和+单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

int longestWPI(vector<int>& hours) {
int len = hours.size();
// hash
for(int i = 0; i < len; i ++ ){
if ( hours[i] > 8) hours[i] = 1;
else hours[i] = -1;
}
// 1, 1, -1, -1, -1, -1, 1
vector<int> sum(len + 1, 0);
for(int i = 1; i <= len; i++ ){
sum[i] = sum[i - 1] + hours[i - 1];
}
stack<int> st;
// 顺序生成单调栈,栈中元素从第一个元素开始严格单调递减,最后一个元素肯定是数组中的最小元素所在位置
for(int i = 0; i <= len; i++ ){
if ( st.empty() || sum[i] < sum[st.top()])
st.push(i);
}


int ans = 0;
/** 常规写法: */
for (int i = len; i >= 0 ; i--) {
while( !st.empty() && sum[st.top()] < sum[i]){
ans = max(ans, i - st.top());
st.pop();
}
}

/** 写法二: */
int i = len;
// 倒序扫描数组,求最大长度坡
while( i > ans){
// sum[st.top()] < sum[i]实际就是找到 sum > 0, 即后面索引j的sum - 前面索引i的sum > 0
while( !st.empty() && sum[st.top()] < sum[i]){
ans = max(ans, i - st.top());
st.pop();
}
i -= 1;
}
return ans;
}

int main(){
vector<int> A = {9,9,6,0,6,6,9};
int ans = longestWPI(A);
cout <<ans <<endl;
return 0;
}
// 此题单调栈具体怎么来的可以看题解: https://leetcode-cn.com/problems/longest-well-performing-interval/solution/can-kao-liao-ji-ge-da-shen-de-ti-jie-zhi-hou-zong-/

参看:Bilibili【带写03】python前缀和与单调栈.mp4

单调队列

P1886 滑动窗口 /【模板】单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

// 这个写法可以借鉴一下
struct node{
int val;
int id; // 下标
};

vector<int> v1; // 最小
vector<int> v2; // 最大

int n, k;
deque<node> q1;
deque<node> q2;


int main(){
cin >> n >> k;
int val;
for (int i = 1; i <= n; i++) {
node nd;
cin >> nd.val;
nd.id = i;

// 如果当前元素小于栈顶元素, 则栈顶元素出栈
// -->获得栈顶小于当前预算
while( !q1.empty() && nd.val <= q1.back().val){
q1.pop_back();
}
while( !q2.empty() && nd.val >= q2.back().val) q2.pop_back();
q1.push_back(nd);
q2.push_back(nd);
if ( i - q1.front().id + 1 > k) q1.pop_front(); // 如果栈底元素已经超出边界则出栈
if ( i - q2.front().id + 1 > k) q2.pop_front();

if (i >= k){ // 当索引满足窗口大小的时候才进行操作
v1.push_back(q1.front().val); // 栈底元素为当前k窗口中最小的
v2.push_back(q2.front().val); // 栈底元素为当前k窗口中最大的
}
}

int len = v1.size();
for (int i = 0; i < len; i++) {
cout << v1[i] << " ";
}
cout << endl;
len = v2.size();
for (int i = 0; i < len; i++) {
cout << v2[i] << " ";
}
return 0;
}

holiday

题目描述

经过几个月辛勤的工作,FJ决定让奶牛放假。

假期可以在1…N天内任意选择一段(需要连续),每一天都有一个享受指数W。但是奶牛的要求非常苛刻,假期不能短于P天,否则奶牛不能得到足够的休息;假期也不能超过Q天,否则奶牛会玩的腻烦。

FJ想知道奶牛们能获得的最大享受指数。

输入格式

第一行:N,P,Q.

第二行:N个数字,中间用一个空格隔开。

输出格式

一个整数,奶牛们能获得的最大享受指数。

样例数据

input

1
2
5 2 4
-9 -4 -3 8 -6

output

1
5

Hint 选择第3-4天,享受指数为-3+8=5。

数据规模与约定

50% 1≤N≤10000,100% 1≤N≤100000

时间限制:1s, 空间限制:256MB

思路:

用前缀和处理前i天的指数和
其实就是从P的位置开始枚举,每次把i-P压入队列,如果i-Q大于队首元素的位置,弹出队首
每次取出队首让ans=max(sum[i]-sum[Day.front()])
最后输出ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define INF 9999999999
long long sum[100300];
int n,p,q;
long long ans=-INF;
deque<long long> Day;

int main(){
freopen("holiday.in","r",stdin);
// freopen("holiday.out","w",stdout);
scanf("%d%d%d",&n,&p,&q);
long long x;
// 前缀和
for(int i=1;i<=n;i++){
scanf("%lld",&x);
sum[i]=sum[i-1]+x;
}

for(int i=p;i<=n;i++){
int nowIndex = i - p;
// 指数和小的放前面
while(!Day.empty() && sum[nowIndex] < sum[Day.back()] ) Day.pop_back();
Day.push_back(nowIndex);
// 实际上应该理解为 当前日期i - 队首的日期 > Q天, 则让pop_front
while(!Day.empty() && i - q > Day.front()) Day.pop_front();
// sum[i] - sum[Day.front()] 为索引i~Day.front()这几天的指数和
ans=max(ans, sum[i]-sum[Day.front()]);
}
cout<<ans;
return 0;
}

总结: 单调队列对于处理线性滑动区间最值可谓游刃有余

借鉴: 数据结构之单调队列与单调栈

单调栈

P2866 [USACO06NOV]Bad Hair Day S

根据题目细品: 第N头牛站最前面, 第1头站最后面, 然后如果Hi > Hn, 则能看到。要求累加第i头牛能看到前面牛的头发数, 即可以理解为第i头牛往前看, 找到比它大的Hi或者边界(边界可以看做为Hi=0的)。===> 输入样例从左往右找比当前元素大的第一个元素,单调递减栈–>正常for i = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f;

int n;
struct cow{
int id;
int height;
};
stack<cow> st;
int main(){
int tmp;
int ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
// C_i的高度
cin >> tmp;
// 找到比当前元素大的一个元素, 期间小的都累计
while( !st.empty() && tmp >= st.top().height ) {
ans += ( i - st.top().id - 1);
st.pop();
}
st.push({i, tmp});
}
// 到最后的时候, 剩下的递减的都是前面没有比自己高的牛了, 如样例最后剩5<-6, 那么6(2)前面没数字了, 所以为0, 5前面(12)只有6了,且6的2高<5的12高, 因此6-5=1有1头牛
while(!st.empty()){
int now = st.top().id;
st.pop();
ans += (n - now);
}
cout << ans <<endl;
return 0;
}

思路2:

  1. 每次输入一头牛的身高,找比这头牛矮的,出栈
  2. 剩下的牛皆可以看到这只牛
  3. ans值加等于栈中牛的个数
  4. 这头牛入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n,t;
long long ans; //注意要开long long
stack <int> a;
int main() {
cin>>n;
for (int i=1; i<=n; i++) {
cin>>t;
// 将栈内删到全都是比t的高的
while (!a.empty() && t >= a.top() )
a.pop();
// 那么栈里的元素都能看到i
ans+=a.size();
// 注意: 先size后push
a.push(t);
}
cout<<ans;
return 0;
}

气温 列表 #739 每日温度

从左往右找比当前元素大的–>如果当前元素比栈顶元素大,那么栈顶元素右边比其第一个大的元素就是当前入栈元素—>单调递减栈(从栈底到栈顶递减)–>val > st.top(),正常for i = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int n;
int ans[maxn]; // 答案
struct temperature{
int id;
int tmp;
};
/**
input:
8
73 74 75 71 69 72 76 73
output:
1 1 4 2 1 1 0 0
*/
int main(){
stack<temperature> st;
cin >> n;
int val;
for (int i = 0; i < n; i++) {
cin >> val ;
while ( !st.empty() && val > st.top().tmp ){
ans[st.top().id] = i - st.top().id ;
st.pop();
}
st.push({i, val}); // 塞进去的是索引
}
for (int i = 0; i < n; i++) {
cout <<ans[i] << " ";
}
cout << endl;
return 0;
}

逆序写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int n;
int ans[maxn]; // 答案
struct temperature{
int id;
int tmp;
temperature(){}
temperature(int _id, int _tmp): id(_id), tmp(_tmp){}
};
/**
input:
8
73 74 75 71 69 72 76 73
output:
1 1 4 2 1 1 0 0
*/
int main(){
stack<temperature> st;
cin >> n;
int val;
vector<int> v(n+1);
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
for (int i = n; i >= 1; i--) {
int val = v[i];
while( !st.empty() && val >= st.top().tmp) st.pop();
ans[i] = st.empty()? 0 : st.top().id - i;
st.push(temperature(i, val));
}
for (int i = 0; i < n; i++) {
cout <<ans[i] << " ";
}
cout << endl;
return 0;
}

P5788 【模板】单调栈

模板写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// ▲不知道为啥必须点开洛谷的O2优化才不会被卡后面4个点
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int n;
int main(){
scanf("%d", &n);
vector<int> v;
v.resize(n+1);
stack< pair<int, int> > st;
vector<int> ans(n+1);
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
while( !st.empty() && v[i] > v[st.top().first]){
ans[ st.top().first ] = i;
st.pop();
}
st.push({i, v[i]});
}
// 遍历完的时候栈里其实还有元素
// cout << "size: "<<st.size() << endl;
for (int i = 1; i <= n; i++) {
if ( i == 1) printf("%d", ans[i]);
else printf(" %d", ans[i]);
}
return 0;
}

for遍历倒着写

1
2
3
4
5
6
7
8
//my
for (int i = n; i >= 1 ; i--) {
while( !st.empty() && v[i] >= v[st.top().first]){
st.pop();
}
ans[ i ] = st.empty() ? 0: st.top().first;
st.push({i, v[i]});
}

// 找的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int n,a[3000001],b[3000001];
stack<int> q;//开一个STL的栈 栈里面存的是数的下标即位置
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];//输入
for(int i=n;i>=1;i--){
while(!q.empty() and a[q.top()]<=a[i])//查找第一个大于a[i]的数
q.pop(); //否则就直接出栈
if(q.empty()) //如果最后没有比a[i]大的数
b[i]=0;
else
b[i]=q.top(); //否则就记录下来
q.push(i); //将i入栈
}
for(int i=1;i<=n;i++) cout<<b[i]<<" ";//输出答案 结束
return 0;
}

区别在于: 站内元素是栈顶元素的右边; 而顺着写, 那么栈内元素是栈顶元素的左边, 即栈顶元素为站内元素的右边;同时还有一个区别是: 顺着先能边读边写, 而倒着写必须读完再写

不用v[]的写法, 其实直接可以用stack< pair<int, int> >st来写,可能会更直观一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int n;

int main(){
int val;
scanf("%d", &n);
stack< pair<int, int> > st;
vector<int> ans(n+1);
for (int i = 1; i <= n; i++) {
scanf("%d", &val);
while( !st.empty() && val > st.top().second ){
ans[ st.top().first ] = i;
st.pop();
}
st.push({i, val});
}

for (int i = 1; i <= n; i++) {
if ( i == 1) printf("%d", ans[i]);
else printf(" %d", ans[i]);
}
return 0;
}

总结

单调栈可利用的点:

  • 剩下的元素 跟 当前元素的关系;弹出元素的个数;剩余元素的个数
  • 栈顶 和 当前元素的关系==> 找到第一个比数大、小的

递减栈的while中条件写 val > st.top()的时候pop,正着写和反着写都一样, 但是要注意等于号的区别;顺着写判断条件完全满足题意(利用pop的动作做处理),而逆着则要考虑先后,如气温题,找第一个反而要加等号, 要pop掉直到左边第一个出现。

===

一般情况下,都是写while()里只有pop的,nums[i] < nums[st.peek()]==>st.pop();,则是维护了一个单调递增栈,对于剩下的栈顶元素而言,入栈元素是>=栈顶元素的,并且对于入栈元素而言找到的是左边第一个大于他的数。单调递减栈,则求的是左边第一个比他小的数。 ===> 如果要求右边的,法一:逆序构建单调栈;法二:从栈顶元素的视角来看(赋值在while里面),只不过这种做法最终栈里会有剩余元素,因此需要对记录数组赋初值。如:2055. 蜡烛之间的盘子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public int[] platesBetweenCandles(String s, int[][] queries) {
int len = s.length();
int[] arr = new int[len];

// 当前元素前面拥有的*数
for (int i = 1; i < len; i++) {
char c = s.charAt(i - 1);
if (c == '*') {
arr[i] = arr[i - 1] + 1;
} else {
arr[i] = arr[i - 1];
}
}

Stack<Integer> minSt = new Stack<>();
Stack<Integer> maxSt = new Stack<>();

// 右边下标最小的蜡烛
int[] minRight = new int[len], maxLeft = new int[len];
// 得赋初值
Arrays.fill(minRight, len);
Arrays.fill(maxLeft, -1);

for (int i = 0; i < len; i++) {
char c = s.charAt(i);

// 如果当前是|则最近的就是自己
if ( c == '|'){
minRight[i] = i;
maxLeft[i] = i;
}

// **得入栈
while (!minSt.empty() && c == '|' && s.charAt(minSt.peek()) == '*') {
minRight[minSt.peek()] = i;
minSt.pop();
}
minSt.push(i);

char ch = s.charAt(len - i - 1);
while (!maxSt.empty() && ch == '|' && s.charAt(maxSt.peek()) == '*') {
maxLeft[maxSt.peek()] = len - i - 1;
maxSt.pop();
}
maxSt.push(len - i - 1);
}


int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int l = queries[i][0], r = queries[i][1];
int ll = minRight[l], rr = maxLeft[r];
if (ll < rr) {
ans[i] = arr[rr] - arr[ll];
}else{
ans[i] = 0;
}
}
return ans;
}
}

Author: Mrli

Link: https://nymrli.top/2020/09/08/数据结构——单调栈/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
docsify使用记录
NextPost >
扇区、块/簇
CATALOG
  1. 1. 单调栈Monotone Stack
    1. 1.1. 概念:
    2. 1.2. 场景:
    3. 1.3. Point:
    4. 1.4. 核心思想
    5. 1.5. Code模板:
    6. 1.6. 例题
      1. 1.6.1. Leetcode#496:
      2. 1.6.2. Leetcode #496. 下一个更大元素 I
      3. 1.6.3. Leetcode#962. 最大宽度坡:
      4. 1.6.4. Leetcode#1124:
      5. 1.6.5. 单调队列
        1. 1.6.5.1. P1886 滑动窗口 /【模板】单调队列
        2. 1.6.5.2. holiday
      6. 1.6.6. 单调栈
        1. 1.6.6.1. P2866 [USACO06NOV]Bad Hair Day S
        2. 1.6.6.2. 气温 列表 #739 每日温度
        3. 1.6.6.3. P5788 【模板】单调栈
    7. 1.7. 总结