1 什么是单调栈

顾名思义，栈中的数据有序则可称为单调栈。根据栈中元素的排序规则，又能分成单调递增栈和单调递减栈。

2 动手试试

动手实现个单调递增栈；

public class MonotoneStack extends LinkedList<Integer> {

    @Override
    public void push(Integer integer) {
        while (!isEmpty() && integer > peek()) {
            pop();
        }
        super.push(integer);
    }
}

3 移掉K位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

https://leetcode-cn.com/problems/remove-k-digits/

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stack = new LinkedList<>();
        for (char c : num.toCharArray()) {
            // 保证删除k位数字内单调递减
            while (!stack.isEmpty() && c < stack.getLast() && k > 0) {
                stack.removeLast();
                k--;
            }
            stack.addLast(c);
        }
        // 删除栈内多余的长度
        while (k > 0) {
            stack.removeLast();
            k--;
        }
        StringBuilder builder = new StringBuilder();
        boolean findDigit = false;
        while (!stack.isEmpty()) {
            // 由栈底像栈顶遍历（双向链表），跳过前缀0
            Character c = stack.removeFirst();
            if (c != '0') findDigit = true;
            if (findDigit) builder.append(c);
        }
        return builder.length() == 0 ? "0" : builder.toString();
    }
}

4 去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

https://leetcode-cn.com/problems/remove-duplicate-letters/

class Solution {
    public String removeDuplicateLetters(String s) {
        // 字符计数器
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            int n = count.getOrDefault(c, 0);
            count.put(c, n + 1);
        }
        // 单调递减栈
        Deque<Character> stack = new LinkedList<>();
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            // 栈上存在说明是最优位置，跳过就行
            if (!stack.contains(c)) {
                while (!stack.isEmpty() && c < stack.getLast() && count.get(stack.getLast()) > 0) {
                    stack.removeLast();
                }
                stack.addLast(c);
            }
            count.put(c, count.get(c) - 1);
        }
        StringBuilder builder = new StringBuilder();
        while (!stack.isEmpty()) {
            builder.append(stack.removeFirst());
        }
        return builder.toString();
    }
}

5 拼接最大数

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

https://leetcode-cn.com/problems/create-maximum-number/

class Solution {

    /**
     * 1 枚举k种组合
     * 2 分别计算两个数组k位最大值（单调栈）
     * 3 合并两个最大值数组
     * 4 结果赋值
     */
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] ret = {};
        for (int i = 0; i <= k; i++) {
            // 过滤不合法i
            if (i > nums1.length || k - i > nums2.length) continue;
            int[] max1 = getMaxNum(nums1, i);
            int[] max2 = getMaxNum(nums2, k - i);
            int[] mergeNums = merge(max1, max2);
            ret = isGreater(ret, 0, mergeNums, 0) ? ret : mergeNums;
        }
        return ret;
    }

    /**
     * 单调递增栈，数组模拟
     */
    private int[] getMaxNum(int[] nums, int k) {
        int[] ret = new int[k];
        int cur = 0, sub = nums.length - k;
        for (int n : nums) {
            while (cur > 0 && n > ret[cur - 1] && sub > 0) {
                cur--;
                sub--;
            }
            if (cur < k) {
                ret[cur++] = n;
            } else {
                // 等同pop
                sub--;
            }
        }
        return ret;
    }

    private int[] merge(int[] nums1, int[] nums2) {
        int[] ret = new int[nums1.length + nums2.length];
        int i = 0, j = 0;
        while (i < nums1.length || j < nums2.length) {
            ret[i + j] = isGreater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
        }
        return ret;
    }

    private boolean isGreater(int[] nums1, int i, int[] nums2, int j) {
        if (j == nums2.length) return true;
        if (i == nums1.length) return false;
        if (nums1[i] == nums2[j]) {
            // 当前元素相等，继续比较下一个
            return isGreater(nums1, i + 1, nums2, j + 1);
        }
        return nums1[i] > nums2[j];
    }
}

6 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

https://leetcode-cn.com/problems/trapping-rain-water/

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.getLast()]) {
                // 走势反转，可能出现凹槽
                Integer cur = stack.removeLast();
                if (stack.isEmpty()) {
                    // 最左侧不予处理
                    break;
                }
                Integer left = stack.getLast();
                // 计算水柱宽高
                int w = i - left - 1;
                int h = Math.min(height[left], height[i]) - height[cur];
                res += w * h;
            }
            stack.addLast(i);
        }
        return res;
    }
}

7 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] copy = new int[heights.length + 2];
        // 两端添加哨兵节点
        for (int i = 1; i < copy.length - 1; i++) {
            copy[i] = heights[i - 1];
        }
        Deque<Integer> stack = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < copy.length; i++) {
            // 维护单调栈
            while (!stack.isEmpty() && copy[i] < copy[stack.getLast()]) {
                // 走势反转时，能确定以栈顶元素为高度的最大矩形面积
                int h = copy[stack.removeLast()];
                int w = i - stack.getLast() - 1;
                res = Math.max(res, w * h);
            }
            stack.addLast(i);
        }
        return res;
    }
}