【数据结构】单调栈专题

模板题：830. 单调栈

关键要理解的地方是什么时候就弹出栈顶。本题找的是距离x最近的比x小的数，所以栈里的数如果大于等于x那么就一定不会被用到（因为x比栈顶元素更优），所以可以全部删掉（弹出），最后剩下的栈顶元素就是答案。

#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int stk[N], tt;

int main()
{
    int n;
    scanf("%d", &n);
    while(n -- )
    {
        int x;
        scanf("%d", &x);
        while(tt && stk[tt] >= x) tt -- ;
        if(tt) printf("%d ", stk[tt]);
        else printf("-1 ");
        stk[++ tt] = x;
    }
    return 0;
}

131. 直方图中最大的矩形

本题要利用单调栈来优化时间复杂度。
要找到左边（右边同理）第一个比当前矩形矮的矩形，所以当栈顶元素的高度大于等于当前高度h[i]，那么栈顶元素就一定不会被用到（因为当前高度更优），可以删掉（弹出），重复此操作直到栈顶元素的高度小于当前高度或栈空（无解）为止

小细节：让h[1]与h[n + 1] = 1，确保所有矩形两边都有比其矮的矩形，可以方便处理边界问题。

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
int h[N], l[N], r[N], q[N];

int main()
{
    while(scanf("%d", &n), n)
    {
        for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
        h[0] = h[n + 1] = -1;
        int tt = 0;
        q[0] = 0;
        for(int i = 1; i <= n; i ++ )
        {
            while(h[i] <= h[q[tt]]) tt -- ;
            l[i] = q[tt];
            q[++ tt] = i;
        }

        tt = 0;
        q[0] = n + 1;
        for(int i = n; i; i -- )
        {
            while(h[i] <= h[q[tt]]) tt -- ;
            r[i] = q[tt];
            q[++ tt] = i;
        }

        LL res = 0;
        for(int i = 1; i <= n; i ++ )
            res = max(res, (LL)h[i] * (r[i] - l[i] - 1));
        printf("%lld\n", res);
    }
    return 0;
}

作者：Once.
链接：https://www.acwing.com/activity/content/code/content/3210396/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

LeetCode 456. 132模式

下图来自leetcode评论区“宫水三叶”

自己的话：
k代表的是第二大的元素，用出栈的元素更新k（有元素出栈就代表有更大的元素要入栈，所以k是第二大的元素），栈里的始终是最大的元素。所以当有nums[i] < k就认为找到了一组解。

class Solution {
public:
    bool find132pattern(vector& nums) {
        int k = INT_MIN;
        stack stk;
        for(int i = nums.size() - 1; i >= 0; i -- )
        {
            if(nums[i] < k) return true;
            while(stk.size() && stk.top() < nums[i])
            {
                k = max(k, stk.top());
                stk.pop();
            }
            stk.push(nums[i]);
        }
        return false;
    }
};