单调栈

1.柱状图中最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 leetcode 84

思路：两侧添加边界；维护单调递增栈，遇到小的出栈计算

public int largestRectangleArea(int[] heights) {
        int[] arr = new int[heights.length +2];
        for(int i = 0 ; i <heights.length ; i++){
            arr[i + 1] = heights[i];
        }
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for(int i = 0; i < arr.length; i++){
            while(!stack.isEmpty() && arr[i] < arr[stack.peek()]){
                int high = arr[stack.pop()];
                while(!stack.isEmpty() && arr[stack.peek()] == high){
                    stack.pop();
                }
                int left = stack.peek();
                int area = (i - left - 1) * high;
                res = Math.max(res,area);
            }
            stack.push(i);
        }
        return res;
    }

2.矩阵中最大矩形

转化为柱状图最大面积，每一层计算最大面积

3.移除部分数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 leetcode 402
输入：num = “1432219”, k = 3 输出：“1219” 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

输入：num = “10200”, k = 1 输出：“200” 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

总体思路：保证高位尽可能的小

• 123531这样「高位递增」的数，肯定不会想删高位，高位肯定想尽量小，会尽量删低位。
• 432135这样「高位递减」的数，会想干掉高位，直接让高位变小，效果很好。
• 保持单调递增栈，当前遍历的数比栈顶小，立马删掉栈顶的数，不管后面有没有更大的。
  因为栈顶的数在高位，删掉它，小的顶上，高位变小，变小的幅度大于低位变小。

• tips：删除前导0。 当栈为空且第一个放入元素为0时，即最高位为0，要将其删除

  public String removeKdigits(String nums, int k) {
        Stack<Character> stack = new Stack<>();
  
        for(int i = 0 ; i < nums.length(); i++){
            char num =  nums.charAt(i) ;
            while(!stack.isEmpty() && stack.peek() > num && k > 0){
                stack.pop();
                k--;
            }
            //栈为空且当前字符为 "0" 时，不入栈。取反，就是入栈的条件：
            if(num != '0' || !stack.isEmpty()){
                 stack.push(num);
            }
        }
  
        //保证移除够k位
        while(k-- > 0 && !stack.isEmpty()) stack.pop();
  
        StringBuilder builder = new StringBuilder();
        while(!stack.isEmpty()){
            builder.append(stack.pop());
        }
  
        return  builder.length() == 0 ? "0" : builder.reverse().toString();
    }
  

4.去除重复字母

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

部分单调：元素有重复时，可以pop；元素唯一时，只能放入

• 维护一个计数器记录元素的个数，当元素只剩一个时，不得不压栈
• 维护一个栈中压入的元素，如果栈中已经存在，跳过

public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];  //// 维护一个计数器记录字符串中字符的数量
        boolean[] inStack = new boolean[26];  //栈中元素

        Stack<Character> stack = new Stack<>();

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

        for(char ch : s.toCharArray()){
            cnt[ch - 'a']--; //每遍历过一个字符，都将对应的计数减一

            if(inStack[ch - 'a']) continue; //栈中存在，跳过

            while(!stack.isEmpty() && stack.peek() > ch){
                // 若之后不存在栈顶元素了，则停止 pop
                if(cnt[stack.peek() - 'a'] == 0){
                    break;
                }
                // 若之后还有，则可以 pop
                inStack[stack.pop() - 'a'] = false;
            }

            stack.push(ch);
            visited[ch - 'a'] = true;
        }

        StringBuilder sb = new StringBuilder();

        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

5.拼接最大数（困难）