强化三 stack

575 Decode String

• 题意：s = abc3[a] return abcaaa； s = 3[abc] return abcabcabc

155 Min Stack
下面三个题都是用到单调栈 注意最后可以多添加一个元素直接得到全部结果

84 Largest Rectangle in Histogram

• 维护单调增栈 注意栈里存的是index 单调增是指index对应元素单调增

85 Maximal Rectangle

• 转化成上一个题 对每一行来说 都存在一个histogram

654 Maximum Binary Tree

• 维护单调减栈

575 Decode String

public class Solution {
    /**
     * @param s: an expression includes numbers, letters and brackets
     * @return: a string
     */
    public String expressionExpand(String str) {
        // write your code here
        Stack<String> stack = new Stack<>();
        for(char c : str.toCharArray()){
            if(c==']'){
                String s = "";
                String rep = "";
                while(!s.equals("[")){
                    rep = s+rep;
                    s = stack.pop();
                }
                int count = 0;
                int base = 1;
                while(!stack.isEmpty() && Character.isDigit(stack.peek().toCharArray()[0])){
                    s = stack.pop();
                    count = count + base*Integer.parseInt(s);
                    base = base*10;
                }
                for(int i=0; i<count; i++){
                    stack.push(rep);
                }
            }else{
                stack.push(c+"");
            }
        }
        String result = "";
        while(!stack.isEmpty()){
            result = stack.pop() + result;
        }
        return result;
    }
}

155 Min Stack

class MinStack {
    Stack<Integer> numStack;
    Stack<Integer> minStack;
    int min;
    /** initialize your data structure here. */
    public MinStack() {
        numStack = new Stack<>();
        minStack = new Stack<>();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) {
        numStack.push(x);
        min = Math.min(min, x);
        minStack.push(min);
    }
    
    public void pop() {
        minStack.pop();
        numStack.pop();
        if(!minStack.isEmpty())
            min = minStack.peek();
        else
            min = Integer.MAX_VALUE;
    }
    
    public int top() {
        return numStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

84 Largest Rectangle in Histogram

class Solution {
    public int largestRectangleArea(int[] heights) {
        int result = 0;
        if(heights==null || heights.length==0)
            return result;
        result = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<=heights.length; i++){
            int num = i==heights.length? -1 : heights[i];
            while(!stack.isEmpty() && heights[stack.peek()]>num){
                int index = stack.pop();
                int height = heights[index];
                int area = stack.isEmpty() ? height*(i-(-1)-1) : height*(i-stack.peek()-1);
                result = Math.max(result, area);
            } 
            stack.push(i);
        }
        return result;
    }
}

85 Maximal Rectangle

• 转化成上一个题 对每一行来说 都存在一个histogram

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int result = 0;
        if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
            return result;
        int[] temp = new int[matrix[0].length];
        for(int i=0; i<matrix.length; i++){
            if(i==0){
                for(int j=0; j<matrix[0].length; j++){
                    if(matrix[i][j]=='1')
                        temp[j] = 1;
                    else
                        temp[j] = 0;
                }
            }else{
                for(int j=0; j<matrix[0].length; j++){
                    if(matrix[i][j]=='1')
                        temp[j] = temp[j] + 1;
                    else
                        temp[j] = 0;
                }
            }
            result = Math.max(result, largestRectangleArea(temp));
        }
        return result;
    }
    public int largestRectangleArea(int[] heights) {
        int result = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<=heights.length; i++){
            int num = i==heights.length? -1 : heights[i];
            while(!stack.isEmpty() && heights[stack.peek()]>num){
                int index = stack.pop();
                int height = heights[index];
                int area = stack.isEmpty() ? height*(i-(-1)-1) : height*(i-stack.peek()-1);
                result = Math.max(result, area);
            } 
            stack.push(i);
        }
        return result;
    }
}

654 Maximum Binary Tree

• 维护单调减栈

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Stack<TreeNode> stack = new Stack<>();
        if(nums==null || nums.length==0)
            return null;
        for(int i=0; i<=nums.length; i++){
            TreeNode node = i==nums.length ? new TreeNode(Integer.MAX_VALUE) : new TreeNode(nums[i]);
            while(!stack.isEmpty() && stack.peek().val<node.val){
                TreeNode son = stack.pop();
                if(stack.isEmpty() || node.val<stack.peek().val)
                    node.left = son;
                else
                    stack.peek().right = son;
            }
            stack.push(node);
        }
        return stack.peek().left;
    }
}