单调栈

单调栈与单调队列很相似。首先栈是后进先出的,单调性指的是严格的递增或者递减。

单调栈有以下两个性质:

1、若是单调递增栈,则从栈顶到栈底的元素是严格递增的。若是单调递减栈,则从栈顶到栈底的元素是严格递减的。

2、越靠近栈顶的元素越后进栈。

单调栈与单调队列不同的地方在于栈只能在栈顶操作,因此一般在应用单调栈的地方不限定它的大小,否则会造成元素无法进栈。

元素进栈过程:对于单调递增栈,若当前进栈元素为e,从栈顶开始遍历元素,把小于e或者等于e的元素弹出栈,直接遇到一个大于e的元素或者栈为空为止,然后再把e压入栈中。对于单调递减栈,则每次弹出的是大于e或者等于e的元素。

一个单调递增栈的例子:

进栈元素分别为3,4,2,6,4,5,2,3

3进栈:(3)

3出栈,4进栈:(4)

2进栈:(4,2)

2出栈,4出栈,6进栈:(6)

4进栈:(6,4)

4出栈,5进栈:(6,5)

2进栈:(6,5,2)

2出栈,3进栈:(6,5,3)

以上左端为栈底,右端为栈顶。

以上部分转载自这里

例题:

接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int trap(vector<int>& height)
{
int ans = 0;
stack<int> st;
for (int i = 0; i < height.size(); i++)
{
while (!st.empty() && height[st.top()] < height[i])
{
int cur = st.top();
st.pop();
if (st.empty()) break;
int l = st.top();
int r = i;
int h = min(height[r], height[l]) - height[cur];
ans += (r - l - 1) * h;
}
st.push(i);
}
return 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
class Solution {
public:
//以最大值分界,左边非减,右边非增
int trap(vector<int>& height) {
int n=height.size();
if(n==0) return 0;
int m=max_element(height.begin(),height.end())-height.begin();
//遍历最大值左边
int res=0,cur=height[0];
for(int i=1;i<m;i++)
{
if(height[i]<cur)
res+=cur-height[i];
else
cur=height[i];
}
//遍历最大值右边
cur=height[n-1];
for(int i=n-2;i>m;i--)
{
if(height[i]<cur)
res+=cur-height[i];
else
cur=height[i];
}
return res;
}
};

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
//my solution, but TLE :(
class Solution {
public:
int trap(vector<int>& height) {
stack <int> S;
S.push(0);
int temp = 0, max_h = height[0];
for(int i = 1; i < height.size(); i++){
if(height[i] <= height[S.top()]) S.push(i);
else{
if(height[i] < max_h){
int t = -1, cnt = 0;
while(!S.empty() && height[S.top()] < height[i]){
t = S.top();
S.pop();
temp += (height[i] - height[t]);
cnt++;
}
for(int j = 0; j <= cnt; j++)
S.push(i);
}
else{
int t = -1;
while(!S.empty() && height[S.top()] <= height[i]){
t = S.top();
S.pop();
temp += (max_h - height[t]);
}
S.push(i);
max_h = height[i];
}
}
}
return temp;
}
};