数据结构——单调栈-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构——单调栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前导：

        队列，栈，前面的链接是对普通的栈，和普通的队列的一个讲解，如果没有对普通的栈和队列不了解的小伙伴可以先看看前面链接中的讲解；

什么是单调，一个序列呈递增或者递减，并且没有一个位置违反了这个递增递减的性质，那么这个序列就算单调序列；

单调栈

咱么先讲单调栈，什么是单调栈，知名知其意，栈里面的元素应该是单调的；而单调栈的作用就是去维护它里面的元素成单调性，例如它可以用来找某个元素左右侧最近比他大比他小的元素的位置；下面直接来图片演示他是如何操作的：

初始状态开始入栈：

一直入栈直到索引3时：

现在继续入栈，到索引5，如果直接入栈索引5又破坏了单调性，那么又需要出栈元素：

最后通过，这样的操作之后，最终结果为：

单调栈的作用

单调栈的主要作用是在处理数据序列中，帮助快速解决一些需要维护单调性的问题，例如：
        1. 寻找下一个更大元素或更小元素：单调栈可以用于查找某个元素右侧或左侧的第一个比它大或小的元素，这在解决一些问题中非常有用，比如上图中索引2位置的92右边最近比他小的就是索引3的65；

2.解决其他需要维护单调性的问题：除了上述示例，单调栈还可用于解决其他需要维护单调性的问题，如找到数组中连续子数组的最大或最小值。

等等，这些需要思考问题的过程中来进行转换，而不是死记硬背，这个就像数学一样，你背下了公式，但是你也不一定会做题，所以需要多做题进行来加深自己的逻辑框架。

例题：

这个数据结构直接去实现没有太大的作用，所以选择一个题目进行来讲解：

  leetcode 84

让你求最大矩形的面积，而这个问题就是进行枚举，然后求每一个矩形的面积，而求每一个矩形的面积如何求，那么这里就可以用到单调栈；

如何求该位置的面积：



初始化，单调栈：

然后可能会有疑问，觉得现在还是没有头绪，没关系往后看：

然后继续上面的操作：

而从数组右边开始，就是这样：

同样的维护单调栈的性质，和左边遍历数组的操作一样，我就不画图了；

然后一直进行这样维护单调栈的性质，最终得到结果：

然后通过两个数组得到，每个位置可以得到的最大的矩形面积，然后再枚举一次数组，进行得到最终最大矩形面积：





最终找到题目要求的答案；
int largestRectangleArea(int* heights, int heightsSize){
    int n = heightsSize;
    int l[n + 5], r[n + 5];//创建l，r数组
    int s[n + 5];//创建栈
    memset(s, 0, sizeof(s));//初始化清空栈
    int top = -1;//top = 0，-1都可以，只是有些条件需要变化一下，这是不影响的
    s[++top] = -1;//入栈虚拟位置
    for (int i = 0; i < n; i++) {
        while (top > 0 && heights[s[top]] >= heights[i]) top--;//top > 0,虚拟位置一直存在栈中，就不用再创建新数组来添加虚拟位置,相当于虚拟位置的高度-1在心中
        l[i] = s[top]; //将最近做左边比i位置高度矮的最近位置记录下来
        s[++top] = i; //入栈i，现在的栈已经维护到入栈i位置一样成单调递增
    }
    top = -1;//初始化栈顶指针
    s[++top] = n;//将虚拟位置入栈
    for (int i = n - 1; i >= 0; i--) {//和上面的逻辑一样，就不解释了
        while (top > 0  && heights[s[top]] >= heights[i]) top--;
        r[i] = s[top];
        s[++top] = i;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int sum = heights[i] * (r[i] - l[i] - 1);//枚举找每个位置的最大面积
        ans = fmax(sum, ans);//记录最大矩形面积
    }
    return ans;
}