什么是栈

要弄明白什么是栈，我们需要先举一个生活中的例子。

假如有一个又细又长的圆筒，圆筒一端封闭，另一端开口。往圆筒里放 入乒乓球，先放入的靠近圆筒底部，后放入的靠近圆筒入口。

那么，要想取出这些乒乓球，则只能按照和放入顺序相反的顺序来取，先取出后放入的，再取出先放入的，而不可能把最里面最先放入的乒乓球优先取出。

栈（stack）是一种线性数据结构，它就像一个上图所示的放入乒乓球的 圆筒容器，栈中的元素只能先入后出 （First In Last Out，简称FILO ）。最早进入的元素存放的位置叫作栈底 （bottom），最后进入的元素 存放的位置叫作栈顶 （top）。

栈这种数据结构既可以用数组来实现，也可以用链表来实现。

栈的数组实现如下。

栈的链表实现如下。

那么，栈可以进行哪些操作呢？栈的最基本操作是入栈和出栈，下面让我们来看一看。

栈的基本操作

入栈

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。

这里我们以数组实现为例。

出栈

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

这里我们以数组实现为例。

入栈和出栈操作，时间复杂度分别是多少？

入栈和出栈只会影响到最后一个元素，不涉及其他元素的整体移动，所以无论是以数组还是以链表实

现，入栈、出栈的时间复杂度都是O(1) 。

什么是单调栈

单调递增栈 从栈底到栈顶的元素关键字的大小单调递增；

单调递减栈 从栈底到栈顶的元素关键字的大小单调递减；

适用问题：

要知道单调栈的适用于解决什么样的问题，我们首先需要知道单调栈的作用。单调栈分为单调递增栈和单调递减栈，通过使用单调栈我们可以访问到下一个比他大（小）的元素（或者说可以）。

也就是说在队列或数组中，我们需要通过比较前后元素的大小关系来解决问题时我们通常使用单调栈。

举个栗子

有一个地方要传授武林秘籍，大家要在这一天之前来这里排好队等着学习武林秘籍。来了很多武林高手，但是这个地方的人要根据人来的先后顺序教，先来的学的武功就高深，来的越靠后学的就越差，但是能保证只要来就能学到。假如他们一开始有一个初始的排队顺序和武力水平如下所示，大家可以按照这个初始顺序从前往后学习。

问题来了，武力值高的肯定愿意先学习到高深一点的武功啊，那我就找到前面武力值低的人说：“你别学了，我教你一门武功，然后离开，否则就咔嚓了你✂️”，武力值低的那听就答应了也就只能无可奈何的打印了，从后来的那个人那里哪里学了一门武术就离开了，这样武功高的那个就排在了前面。下面我们来从前往后模拟一下过程：

（1）首先来的是炮灰甲，炮灰甲一看，OK，栈内没有人就可以先排在第一位

（2）然后扫地僧来了，扫地僧教给了炮灰甲一招易筋经，然后扫地僧让炮灰甲离开自己排在第一位。

（3）然后杨过过来，看到前面是扫地僧，自己打不过只能老老实实站到队里。

（4）后面一直来人（如3）------ 直到张三 对里面站的是 扫地僧 杨过 慕容复 张三 。

（5）然后张无忌来了，他首先看到前面是张三，张无忌教给张三一招武当梯云纵，然后让张三离开了，张无忌再往前看到了慕容复教他一招太极拳，然后继续直到遇到扫地僧，OK，自己打不过，老老实实的占到了后面 —现在队里有扫地僧，张无忌 ----杨过，慕容复，张三的师傅为张无忌

（6）柯镇恶来了，打不过，站到后面就好了。

（7）然后乔峰来了把柯镇恶和张无忌打发走， —现在队里有扫地僧，乔峰。

（8）然后李四来了，打不过乔峰，只能站到了最后。

（9）第二天扫地僧，乔峰，李四成功学到了武林秘籍

现在看他们分别学到武功对应如下图：

这样我们就处理完了所有过程。因此单调栈的时间复杂度为O(n),在比较时对出栈的元素有一个处理（例如扫地僧让炮灰甲走的时候教给他自己的武功），另外最后留在站内的元素有一个统一的处理（扫地僧，乔峰，李四成功学到了武林秘籍）。

伪代码如下所示：

对于第i个到来的人：

• 每当队里面有人并且打不过自己的时候：

• • 让这个人离开并交给他自己的武功
  • 自己入队

LCR 039. 柱状图中最大的矩形

思路：有了单调栈的基本认识，我们可以遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。对于每个柱子我们都如上计算一遍以当前柱子作为高的矩形面积，最终比较出最大的矩形面积即可。

单调栈实现：寻找两边距离arr[i]最近且arr[i]小的索引，保持栈顶到栈底单调递减，栈中存放索引值。

注意：头0如果不添加，寻找左边元素需要判断栈是否为空；尾0如果不添加，需要重新写一个循环弹出栈内元素。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int [] left = new int[n];
        int [] right = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++){
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                stack.pop();
            }
            left[i] = (stack.isEmpty() ? -1: stack.peek());
            stack.push(i);
        }
        stack.clear();
        for(int i = n-1; i >= 0; i--){
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                stack.pop();
            }
            right[i] = (stack.isEmpty() ? n : stack.peek());
            stack.push(i);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }
}

42.接雨水

该题目有多种解法，本次只介绍单调栈的方式，对其它算法感兴趣的朋友可以自己去尝试一下~~

思路：理解题目注意题目的性质，当后面的柱子高度比前面的低时，是无法接雨水的，当找到一根比前面高的柱子，就可以计算接到的雨水。所以使用单调递减栈：

• 对更低的柱子入栈，更低的柱子以为这后面如果能找到高柱子(可以理解为 代码中的 left )，这里就能接到雨水，所以入栈把它保存起来。
• 当出现高于栈顶（代码中 top）的柱子时说明可以对前面的柱子结算了

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }
}