这里标注一下，本文参考于 《labuladong的算法小抄》

1. 思想讲解

1.1 单调栈思想

单调栈顾名思义栈中的元素在某一方面呈单调趋势，栈中存的可以是相应的数组值，也可以是相应的数组值的下标。但是平时的题目没有相关的提醒，所以有时候很难看出是单调栈，所以我们刷题时遇到具有明显的单调性需要留一个心眼。

1.2 那我们是怎样维护这个栈的呢？

模板解析：

核心思想很简单，其实就是怎样维护这个栈。我们对每一个数组元素和栈顶比较大小（如果维护的是单调递增栈，那么该数组元素大于栈顶元素就入栈，如果是该数组元素是小于等于栈顶元素，那么就对栈内元素进行出栈操作。维护的其他的类型栈操作类似）。

（1）、单调递减栈 ： 求的是下一个更大的元素

for(int i = num.length - 1; i >= 0; i --){
   while(!s.isEmpty() && num[i] >= s.peek()){
        s.pop();
    }
    s.push(num[i]);
}

（2）、单调递增栈 ： 求的是下一个更小的元素

for(int i = num.length - 1; i >= 0; i --){
    while(!s.isEmpty() && num[i] <= s.peek()){
        s.pop();
    }
    s.push(num[i]);
}

（3）、维护的是一个单调递减栈

for(int i = 0; i < num.length; i ++){
    while(!s.isEmpty() && num[i] > s.peek()){
        s.pop();
    }
    s.push(num[i]);
}

（4）、 维护的是一个单调递增栈

for(int i = 0; i < num.length; i ++){
    while(!s.isEmpty() && num[i] > s.peek()){
        s.pop();
    }
    s.push(num[i]);
}

2. 例题讲解

2.1 接雨水

AC代码：

public int trap(int[] height) {
        int ans = 0;
        Stack<Integer> s = new Stack<>();

        for(int i = 0; i < height.length; i ++){
            while(!s.isEmpty() && height[s.peek()] < height[i]){
                int index = s.pop();

                if(s.isEmpty()) break;

                int left = s.peek();

                int min = Math.min(height[i],height[left]);
                ans += (min - height[index]) * (i - left - 1);           
            }
            s.push(i);
        }
        return ans;
    }

题目解析：

为什么该题可以使用单调栈？
分析题意可知，只有当呈凹字状的才能接住雨水，所以在一系列的单调不增的数中，突然出现了一个数比前面的数大的话，我们就需要对前面的数进行结算。所以可以使用单调栈。

结算时的第一种情况

图中所标注的是下标，栈中存放的也是下标。且该种情况接不到雨水。

为什么在内层循环中需要设置以下代码？

if(s.isEmpty()) break;

当第一个元素的下标已经进栈，第二个的元素大于栈顶元素进入内层循环。栈对栈顶元素进行pop()，并且此时栈为空，我们需要对后面的代码进行终止。所以设置以上代码。

结算时的第二种情况

图中所标注的是下标，且该种情况下的所接雨水为4。

当程序运行到下图所示：

准备进栈的元素为下标为4的元素，此时它的值比栈顶元素的大。

执行以下代码：

int index = s.pop();

if(s.isEmpty()) break;

int left = s.peek();

int min = Math.min(height[i],height[left]);
ans += (min - height[index]) * (i - left - 1);

此时的index为3，left为2，求出来的雨水量为1。

此时如下图所示：

如上图所示的栈中元素还要经过一次的对4的pop，因为求出的雨水量为0，所以此处省略。那么就是如上图所示了。

执行以下代码：

int index = s.pop();

if(s.isEmpty()) break;

int left = s.peek();

int min = Math.min(height[i],height[left]);
ans += (min - height[index]) * (i - left - 1);

此时的index为2，left为1，求出来的雨水量为3。

所以此时的总雨水量为4。

2.2 柱状图中最大的矩形

题目解析
这是一道在竞赛中算简单的，但在笔试面试中属于难的题目。其实想明白了也就很简单了。我们对数组中的每一个元素进行处理出左边和右边的下一个更小的元素的下标，那么这道题也就解决了。

那么为什么如上所说就解决了？

因为假如我们情况如图所示：

左右两边的比它高的不会影响它的最大面积的扩展，只有当是高度小于它的时候才会影响。

找到左边第一个比它小的数

int[] l = new int[heights.length];
Stack<Integer> s1 = new Stack<>();
 for(int i = 0; i < heights.length; i ++){
    while(!s1.isEmpty() && heights[i] <= heights[s1.peek()]){
        s1.pop();
    }
    l[i] = s1.isEmpty() == true ? -1 : s1.peek();
    s1.push(i); 
}

为什么栈空就设置为-1 ？

l[i] = s1.isEmpty() == true ? -1 : s1.peek();

因为此时左边没有元素比它小，所以设为最左边的 -1呗

找到右边第一个比它小的数

int[] r = new int[heights.length];
Stack<Integer> s2 = new Stack<>();
for(int i = heights.length - 1; i >= 0; i --){
   while(!s2.isEmpty() && heights[i] <= heights[s2.peek()]){
        s2.pop();
    }
    r[i] = s2.isEmpty() == true ? heights.length : s2.peek();
    s2.push(i);
}

为什么栈空设为heights.length?

因为右边没有比它更小的元素了，所以设置为heights.length。

相应的面积计算

res,heights[i] * (r[i] - l[i] - 1);

AC代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] l = new int[heights.length];
        Stack<Integer> s1 = new Stack<>();
        int[] r = new int[heights.length];
        
        Stack<Integer> s2 = new Stack<>();

        // 找到左边第一个比它小的数，组成一个下标数组
        for(int i = 0; i < heights.length; i ++){
            while(!s1.isEmpty() && heights[i] <= heights[s1.peek()]){
                s1.pop();
            }
            l[i] = s1.isEmpty() == true ? -1 : s1.peek();
            s1.push(i); 
        }

        // 找到右边第一个比它小的数组成一个下标数组。
        for(int i = heights.length - 1; i >= 0; i --){
            while(!s2.isEmpty() && heights[i] <= heights[s2.peek()]){
                s2.pop();
            }
            r[i] = s2.isEmpty() == true ? heights.length : s2.peek();
            s2.push(i);
        }

        // 以数组每个点作为高更新res
        int res = 0;
        for(int i = 0; i < heights.length; i ++){
            res = Math.max(res,heights[i] * (r[i] - l[i] - 1));
        }

        return res;
    }
}

3. 相关 LeetCode 题目

3.1 移掉 K 位数字

题目分析：
很明显，需要返回的是一个数值最小的数字，维护的是一个单调递增栈，就是需要注意的是它这个k个元素必须去除和要防止前导零的出现。

AC代码：

class Solution {
    public String removeKdigits(String num, int k) {
        // 由于k 是必须要去除的 k个元素
        if(num.length() <= k) return "0";

        Deque<Character> queue = new LinkedList<>();

        for(int i = 0; i < num.length(); i ++){
            char c = num.charAt(i);

            while(!queue.isEmpty() && queue.peekLast() > c){
                // 为什么此处的 是 > ?
                // 这里需要注意的是 维护的是一个 单调不减栈,因为可能出现后面一个和前面的栈中的一个元素相等，但是其实前面的一个位于前面，后面返回值都不会影响，所以此处设置为维护的是一个单调不减栈。

                if(k <= 0){
                    break;
                }
                // 此处的break 应该很好理解
                queue.pollLast();
                k --;
            }

            queue.offerLast(c);
        }

        // 为什么此处要设置这一个while循环呢？
        // 因为题目要求必须去除k个元素，但是我们知道满足前面要求的不一定都除去过了k个元素了，
        // 比如 num = "112", k = 1;
        // 运行到此处是 sb = "112",显而易见有必要设置这样一个循环。
        while(k > 0){
            queue.pollLast();
            k --;
        }

        StringBuffer sb = new StringBuffer();

        while(!queue.isEmpty()){
            sb.append(queue.pollFirst());
        }

        while(sb.length() > 1 && sb.charAt(0) == '0'){
            sb.deleteCharAt(0);
        }

        return new String(sb);
    }
}

注意点：

1. 这个k个元素必须去除

// 由于k 是必须要去除的 k个元素
if(num.length() <= k) return "0";

2. 为什么此处要设置这一个while循环呢？

while(k > 0){
   queue.pollLast();
     k --;
 }

因为题目要求必须去除k个元素，但是我们知道满足前面要求的不一定都除去过了k个元素了，比如 num = “112”, k = 1;运行到此处是 sb = “112”, 显而易见有必要设置这样一个循环。

3. 为什么需要在内层循环中设置break？

因为最多去除k个字符。

3.2 去除重复字母

AC代码：

class Solution {
    public String removeDuplicateLetters(String s) {
        // 1.其实这题是单调栈的思想，但是我们为什么使用的是双端队列的这种数据结构呢？
        // 因为最后结果返回的是一个字符串，而需要进行前端出，但在处理过程中有需要进行后端出元素的操作，所以使用双端队列
        // 2.但为什么我们不能事先处理字符串呢？
        // 因为需要进行去重，但是我们又不能事先处理好字符串。因为我们不知道事先对那个多余的字符进行删除，而题目又要保证字符的相对顺序，所以不能事先去重。所以我们设置一个去重数组 inQueue[],判断是否在队列中。和回溯时的去重相似
        // 3.那为什么又要设置 count[] 数组呢？
        // 根据单调栈的套路，我们每一次需要对栈中的元素进行出栈，但是这仅仅是因为前面的字符大于等于后面要入栈的字符。而因为我们是从前往后遍历的s字符串，而当这个字符在我们后面的字符子串不再出现，而又将要出栈，我们要对此行为进行阻止。所以设置count[] 数组计数

        // 特别注意点
        // （1）、在元素进队列的时候，我们需要对 count[] 和 inQueue[] 中的相应值进行修改
        // （2）、就算队列中已经存在相应的元素了，我们也需要对 count[]中的数值修改，前已经说明了 count[]的含义，这里应该很好明白。

        Deque<Character> queue = new LinkedList<>();

        int[] count = new int[26];
        boolean[] inQueue = new boolean[26];

        for(int i = 0; i < s.length(); i ++){
            char c = s.charAt(i);
            count[c - 'a'] ++;
        }

        for(int i = 0; i < s.length(); i ++){
            char a = s.charAt(i);

            if(inQueue[a - 'a'] == true){
                count[a - 'a'] --;
                continue;
            }

            while(!queue.isEmpty() && queue.peekLast() >= a){

                if(count[queue.peekLast() - 'a'] == 0) break;

                char b = queue.pollLast();
                inQueue[b - 'a'] = false;

            }

            queue.offerLast(a);
            inQueue[a - 'a'] = true;
            count[a - 'a'] --;
        }

        StringBuffer sb = new StringBuffer();

        while(!queue.isEmpty()){
            sb.append(queue.pollFirst());
        }

        return new String(sb);
    }
}

题目代码解析：

1. 其实这题是单调栈的思想，但是我们为什么使用的是双端队列的这种数据结构呢？

因为最后结果返回的是一个字符串，而需要进行前端出，但在处理过程中有需要进行后端出元素的操作，所以使用双端队列。

2.但为什么我们不能事先处理字符串呢？

因为需要进行去重，但是我们又不能事先处理好字符串。因为我们不知道事先对那个多余的字符进行删除，而题目又要保证字符的相对顺序，所以不能事先去重。 所以我们设置一个去重数组 inQueue[],判断是否在队列中。和回溯时的去重相似

3.那为什么又要设置 count[] 数组呢？

根据单调栈的套路，我们每一次需要对栈中的元素进行出栈，但是这仅仅是因为前面的字符大于等于后面要入栈的字符。而因为我们是从前往后遍历的s字符串，而当这个字符在我们后面的字符子串不再出现，而又将要出栈，我们要对此行为进行阻止。所以设置count[] 数组计数。

4.特别注意点

（1）、在元素进队列的时候，我们需要对count[] 和 inQueue[] 中的相应值进行修改。

（2）、就算队列中已经存在相应的元素了，我们也需要对 count[]中的数值修改，前已经说明了 count[]的含义，这里应该很好明白。