Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Largest Rectangle in Histogram 升级版。对于矩阵每行，可以看成是这个问题。height array对于相邻的行，假如当前的matrix[i][j] = 0，则无视上一行且当前height[j] = 0，如果matrix[i][j] = 1，则加上之前的height[j] += 1。

public class Solution {
    //Time: O(m*n)  Space: O(n)
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int max = 0;
        int[] height = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            int cur = largestRectangleArea(height);
            max = Math.max(max, cur);
        }
        return max;
    }
    
    public int largestRectangleArea(int[] height) {
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= height.length; i++) {
            int h = i == height.length ? -1 : height[i];
            while (!stack.isEmpty() && h < height[stack.peek()]) {
                int index = stack.pop();
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, w * height[index]);
            }
            stack.push(i);
        }
        return max;
    }
}

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

我们需要维护一个递增的stack。

举例现在在stack里是1，3，5，7。现在来了4，说明以7为高度生成矩阵已经不可能在增长了。把7pop出来，算出以7为高的矩阵和全局比较。在继续这么比较。在数组最后push -1进去，使stack里剩余的高度都能被计算。实际在stack里是高度对应的Index，不是高度本身。宽度：当stack已经为空了则为当前要push的i，否则为i - stack.peek() - 1。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= height.length; i++) {
            int h = i != height.length ? height[i] : -1;
            while (!stack.isEmpty() && height[stack.peek()] > h) {
                int index = stack.pop();
                int w = stack.isEmpty() ? i : (i - stack.peek() - 1);
                max = Math.max(max, height[index] * w);
            }
            stack.push(i);
        }
        return max;
    }
}

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3

   / \

  9  20

     /    \

   15   7

return its zigzag level order traversal as:

[

  [3],

  [20,9],

  [15,7]

]

BFS: 用两个stack来实现层遍历

public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> cur = new Stack<TreeNode>();
        Stack<TreeNode> next = new Stack<TreeNode>();
        cur.push(root);
        boolean reverse = true;
        
        while (!cur.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            while (!cur.isEmpty()) {
                TreeNode node = cur.pop();
                if (reverse) {
                    if (node.left != null) {
                        next.push(node.left);
                    }
                    if (node.right != null) {
                        next.push(node.right);
                    }
                } else {
                    if (node.right != null) {
                        next.push(node.right);
                    }
                    if (node.left != null) {
                        next.push(node.left);
                    }
                }
                level.add(node.val);
            }
            reverse = !reverse;
            Stack<TreeNode> temp = cur;
            cur = next;
            next = temp;
            res.add(level);
        }
        return res;
    }
}

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

用一个stack，如果是括号左边push，右边就和pop出来的比较是否为一对（检查stack是否已经为空）。最后检查遍历完后，stack是否为空。

public class Solution {
    //Time: O(n)
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        HashMap<Character, Character> map = new HashMap<Character, Character>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<Character>();
        
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty() || map.get(stack.peek()) != s.charAt(i)) {
                    return false;
                }
                stack.pop();
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

Binary Tree Inorder/Preorder/Postorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1

    \

     2

    /

   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Recursion:

public class Solution {
    //Time: O(n)  Space: O(depth of tree)
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
    
    private void inorder(TreeNode root, ArrayList<Integer> res) {
        if (root == null) {
            return;
        }
        //res.add(root.val);  pre
        inorder(root.left, res);
        //res.add(root.val);  in
        inorder(root.right, res);
        //res.add(root.val);  post
    }
}

Iterative: Inorder
使用一个stack，如果有左子树，就把当前点放进stack，反之pop出一个node，检查它的右子树。

public class Solution {
    //Time: O(n)  Space: O(depth of tree)
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while (!stack.isEmpty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                res.add(p.val);
                p = p.right;
            }
        }
        return res;
    }
}

Iterative: Preorder
用一个stack，当前node被pop出后，先push右子树节点，再push左子树节点

public class Solution {
    //Time: O(n)  Space: O(n)
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.right != null) { //push right first
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
            res.add(cur.val);
        }
        return res;
    }
}

Iterative: Postorder

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        TreeNode cur = root;
        stack.push(root);
        while (!stack.isEmpty()) {
            cur = stack.peek();
            if (pre == null || pre.left == cur || pre.right == cur) {
                if (cur.left != null) {
                    stack.push(cur.left);
                } else if (cur.right != null) {
                    stack.push(cur.right);
                }
            } else if (cur.left == pre) {
                if (cur.right != null) {
                    stack.push(cur.right);
                }
            } else {
                res.add(cur.val);
                stack.pop();
            }
            pre = cur;
        }
        return res;
    }
}