单调栈

单调栈

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

单调栈有以下两个性质：

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;
    }
};