Using Stack - Algorithm


Stack
- Use stack to change operation order
- Ordered stack
  -- push to stack if condition is true newElement <(or>) peek, otherwise pop stack until the condition is false
- Use LinkedList: can be used as a Queue or Stack (Printing a Binary Tree in Zig Zag Level-Order)
- Usually we can also use recursion
  -- Determined by whether whether the recursion is much easier and how is the performance, what states to maintain, whether it has implicit performance penalty: such as substring, indexOf
LeetCode 232 - Implement Queue using Stacks
http://codercareer.blogspot.com/2013/02/no-39-stacks-sharing-array.html

Implement 3/k stacks in 1 array

LeetCode 20 - Valid Parentheses

X. Using stack
LeetCode 439 - Ternary Expression Parser
- Recursion
http://hongzheng.me/leetcode/leetcode-439-ternary-expression-parser/

LeetCode 636 - Exclusive Time of Functions

X. Using 2 stacks
Lintcode - Expression Tree Build
    public ExpressionTreeNode build(String[] expression) {
        Stack ops = new Stack<>();
        Stack data = new Stack<>();
        for( int i = 0; i < expression.length; i++) {
            String str = expression[i];
            if(str.equals("+") || str.equals("-") ||str.equals("*") ||str.equals("/")) {
                while(!ops.isEmpty() && operatorLevel(ops.peek().symbol) >= operatorLevel(str)) {
                    newNodeGtr(ops, data);
                }
                ops.push(new ExpressionTreeNode(str));
            }else if(str.equals("(")){
                ops.push(new ExpressionTreeNode(str));
            }else if(str.equals(")")) {
                while(!ops.isEmpty() && !ops.peek().symbol.equals("("))
                    newNodeGtr(ops, data);
                if(!ops.isEmpty()) 
                    ops.pop(); // pop the "("
            }else
                data.push(new ExpressionTreeNode(str));
        }

        while(!ops.isEmpty())
            newNodeGtr(ops, data);

        return data.isEmpty()? null : data.pop();
    }
Expression Evaluation

LeetCode 394 - Decode String
s = "3[a2[c]]", return "accaccacc".
countStack, stringStack
count, curString
or class StrItem {
    int num = 0;
    StringBuilder sb
}
Stack
    public String decodeString(String s) {
        Stack count = new Stack<>();
        Stack result = new Stack<>();
        int i = 0;
        result.push("");
        while (i < s.length()) {
            char ch = s.charAt(i);
            if (ch >= '0' && ch <= '9') {
                int start = i;
                while (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') i++;
                count.push(Integer.parseInt(s.substring(start, i + 1)));
            } else if (ch == '[') {
                result.push("");
            } else if (ch == ']') {
                String str = result.pop();
                StringBuilder sb = new StringBuilder();
                int times = count.pop();
                for (int j = 0; j < times; j += 1) {
                    sb.append(str);
                }
                result.push(result.pop() + sb.toString());
            } else {
                result.push(result.pop() + ch);
            }
            i += 1;
        }
        return result.pop();
    }
- Using Recursion

X. Ordered stack
print the nearest larger element for each element.


LeetCode 32 - Longest Valid Parentheses
Largest Rectangular Area in a Histogram

LeetCode 84 - Largest Rectangle in Histogram
- Ordered Stack

Stack Reversal

LeetCode 71 - Simplify Path
- Using Double Queue LinkedList

TODO LeetCode 385 - Mini Parser
- NestedInteger
- Using Stack
- Recursion
    public NestedInteger deserialize(String s) {
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        NestedInteger result = new NestedInteger();
        helper(s, 1, result);//1
        return result;
    }

    private int helper(String s, int idx, NestedInteger parent) {
        int l = idx, r = idx;
        while (r < s.length()) {
            String num = s.substring(l, r);//don't do here
            if (s.charAt(r) == '[') {
                NestedInteger child = new NestedInteger();
                parent.add(child);
                r = helper(s, r + 1, child);//
                l = r;
            } else if (s.charAt(r) == ']') { // get num here
                if (!num.isEmpty()) parent.add(new NestedInteger(Integer.valueOf(num)));
                return r + 1;//
            } else if (s.charAt(r) == ',') {//get num here
                if (!num.isEmpty()) parent.add(new NestedInteger(Integer.valueOf(num)));
                r++;
                l = r;
            } else {
                r++;
            }
        }
        return s.length();//
    }
- Recursion 2

LeeCode 341 - Flatten Nested List Iterator
- stack of ListIterators
- keep an additional field storing the next integer
- Stack> stack, Integer nextInteger
- Stack stack

LeetCode 339 - Nested List Weight Sum
https://leetcode.com/discuss/94956/2ms-easy-to-understand-java-solution
- Recursion
- BFS
- Using Stack

LeetCode 364 - Nested List Weight Sum II
- DFS
int(this layer sum) DFS(List nestedList, int preLayerSum)
- BFS unweighted, weighted
add unweighted integers multiple times
prev += levelSum;
total += prev;
- Find depth first

Design a deep iterator
private Stack iteratorStack = new Stack();
private Integer top = null;
    private Stack iteratorStack = new Stack();
    private Integer top = null;

    public DeepIterator(Iterable iterable){
        this.iteratorStack.push(iterable.iterator());
    }
    public boolean hasNext() {
        if(this.top != null) return true;

        while(!this.iteratorStack.isEmpty()) {
            Iterator tmpIterator = this.iteratorStack.peek();

            if(tmpIterator.hasNext()){
                Object tmp = tmpIterator.next();
                if(tmp instanceof Integer){
                    this.top = (Integer) tmp;
                    return true;
                } else if(tmp instanceof Iterable){
                    this.iteratorStack.push(((Iterable) tmp).iterator());
                } else {
                    throw new RuntimeException("Unsupported data type. ");
                }
            } else {
                this.iteratorStack.pop();
            }
        }
        return false;
    }

LeetCode 103 - Printing a Binary Tree in Zig Zag Level-Order
- Using two stacks
     if(d==0){
      if (node.left != null) next_layer.push(node.left);
      if (node.right != null) next_layer.push(node.right);
     }else{
      if (node.right != null) next_layer.push(node.right);
      if (node.left != null) next_layer.push(node.left);
     }
- Using DoubleQueue LinkedList
- Using DFS
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length, next[] = new int[n];
        Arrays.fill(next, -1);
        Stack stack = new Stack<>(); // index stack
        for (int i = 0; i < n * 2; i++) {
            int num = nums[i % n]; 
            while (!stack.isEmpty() && nums[stack.peek()] < num)
                next[stack.pop()] = num;
            if (i < n) stack.push(i);//
        }   
        return next;
    }


X. Ordered stack
Leetcode 316 - Remove Duplicate Letters
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
All characters in stack are increasing
- Ordered Stack: stack, freqMap or count[], boolean[] visited
- Recursion O(KN)
- Stack A2: Map lastPosMap

Lintcode 126 - Max Tree
Given an integer array with no duplicates. A max tree building on this array is defined as follow:
  • The root is the maximum number in the array
  • The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.
http://blog.welkinlan.com/2015/06/29/max-tree-lintcode-java/
    public TreeNode maxTree(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return null;
        }
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        for (int i = 0; i < A.length; i++) {
            TreeNode cur = new TreeNode(A[i]);
            while (!stack.isEmpty() && cur.val > stack.peek().val) {
                cur.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }
            stack.push(cur);
        }
        TreeNode result = new TreeNode(0);
        while (!stack.isEmpty()) {
            result = stack.pop();
        }
        return result;
    }

LeetCode 84 - Largest Rectangle in Histogram
https://discuss.leetcode.com/topic/7599/o-n-stack-based-java-solution
    public int largestRectangleArea(int[] height) {
        int len = height.length;
        Stack s = new Stack();
        int maxArea = 0;
        for(int i = 0; i <= len; i++){
            int h = (i == len ? 0 : height[i]);
            if(s.isEmpty() || h >= height[s.peek()]){
                s.push(i);
            }else{
                int tp = s.pop();
                maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }
Left, right array:
https://discuss.leetcode.com/topic/48127/java-o-n-left-right-arrays-solution-4ms-beats-96

Leetcode 85 - Maximal Rectangle
https://discuss.leetcode.com/topic/21772/my-java-solution-based-on-maximum-rectangle-in-histogram-with-explanation
public int maximalRectangle(char[][] matrix) {
    if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
    
    int[] height = new int[matrix[0].length];
    for(int i = 0; i < matrix[0].length; i ++){
        if(matrix[0][i] == '1') height[i] = 1;
    }
    int result = largestInLine(height);
    for(int i = 1; i < matrix.length; i ++){
        resetHeight(matrix, height, i);
        result = Math.max(result, largestInLine(height));
    }
    
    return result;
}

private void resetHeight(char[][] matrix, int[] height, int idx){
    for(int i = 0; i < matrix[0].length; i ++){
        if(matrix[idx][i] == '1') height[i] += 1;
        else height[i] = 0;
    }
}    

public int largestInLine(int[] height) {
    if(height == null || height.length == 0) return 0;
    int len = height.length;
    Stack s = new Stack();
    int maxArea = 0;
    for(int i = 0; i <= len; i++){
        int h = (i == len ? 0 : height[i]);
        if(s.isEmpty() || h >= height[s.peek()]){
            s.push(i);
        }else{
            int tp = s.pop();
            maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
            i--;
        }
    }
    return maxArea;
}
TODO
https://discuss.leetcode.com/topic/6650/share-my-dp-solution
http://www.voidcn.com/blog/meisen1124/article/p-4593005.html
https://discuss.leetcode.com/topic/36200/o-n-2-dp-java-solution
public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[] left = new int[n]; // left boundary of histogram columns.
        int[] right = new int[n]; // right boundary of histogram columns.
        int[] height = new int[n]; // height of histogram columns.
        Arrays.fill(right, n);
        int area = 0;
        for (int i = 0; i < m; i++) {
            int l = 0, r = n;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    height[j]++;
                    left[j] = Math.max(l, left[j]);
                }
                else {
                    l = j + 1;
                    height[j] = 0;
                    left[j] = 0;
                    right[j] = n;
                }
            }
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = Math.min(r, right[j]);
                    area = Math.max(area, height[j] * (right[j] - left[j]));
                }
                else {
                    r = j;
                }
            }
        }
        return area;
    }
LeetCode 42 - Trapping Rain Water
https://discuss.leetcode.com/topic/4939/a-stack-based-solution-for-reference-inspired-by-histogram
https://discuss.leetcode.com/topic/29113/java-with-stack-following-the-approach-similar-to-largest-rectangle-in-histogram
public int trap(int[] A) {
        if (A==null) return 0;
        Stack s = new Stack();
        int i = 0, maxWater = 0, maxBotWater = 0;
        while (i < A.length){
            if (s.isEmpty() || A[i]<=A[s.peek()]){
                s.push(i++);
            }
            else {
                int bot = s.pop();
                maxBotWater = s.isEmpty()? // empty means no il
                0:(Math.min(A[s.peek()],A[i])-A[bot])*(i-s.peek()-1);
                maxWater += maxBotWater;
            }
        }
        return maxWater;
    }
LeetCode 103 - Printing a Binary Tree in Zig Zag Level-Order
https://discuss.leetcode.com/topic/3318/my-ac-java-code
public List<List> zigzagLevelOrder(TreeNode root) {
    List<List> output = new ArrayList<List>();
    if (root == null) return output;
    Stack cur_layer = new Stack(); cur_layer.push(root);
    Stack next_layer = new Stack();
    List layer_output = new ArrayList();
    int d = 0; // 0: left to right; 1: right to left.
    
    while (!cur_layer.isEmpty()){
     TreeNode node = cur_layer.pop();
     layer_output.add(node.val);
     if(d==0){
      if (node.left != null) next_layer.push(node.left);
      if (node.right != null) next_layer.push(node.right);
     }else{
      if (node.right != null) next_layer.push(node.right);
      if (node.left != null) next_layer.push(node.left);
     }
     
     if (cur_layer.isEmpty()){
      output.add(layer_output);
      layer_output = new ArrayList();
      cur_layer = next_layer;
      next_layer = new Stack();;
      d ^= 1;
     }
    }
    return output;
}
BFS https://discuss.leetcode.com/topic/42184/java-easy-understand-recursive-methods-beats-96-attach-easy-bfs-methods
https://discuss.leetcode.com/topic/44739/java-iterative-and-recursive-solutions
  public List<List> zigzagLevelOrder(TreeNode root) {
    List<List> res = new ArrayList<>();
    if(root == null)
        return res;
    
    Queue q = new LinkedList<>();
    q.offer(root);
    int level = 1;
    while(!q.isEmpty()){
        LinkedList path = new LinkedList<>();
        int levelNums = q.size();
        
        for(int i = 0; i < levelNums; i++){
            root = q.poll();
            if(level % 2 != 0){
                path.add(root.val);
            }else{
                path.addFirst(root.val);
            }
            
            if(root.left != null)
                q.offer(root.left);
            if(root.right != null)
                q.offer(root.right);
        }
        res.add(path);
        level++;
    }
    
    return res;
}
https://discuss.leetcode.com/topic/40067/my-java-solution-beats-98
public List<List> zigzagLevelOrder(TreeNode root) {
    List<List> res = new ArrayList();
    travel(res, 0, root);
    return res;
}
private void travel(List<List> res, int level, TreeNode cur) {
    if (cur == null) return;
    if (res.size() <= level) {
        res.add(new ArrayList());
    }
    if (level % 2 == 0) {
        res.get(level).add(cur.val);
    }   else {
        res.get(level).add(0, cur.val);
    }
    travel(res, level + 1, cur.left);
    travel(res, level + 1, cur.right);
}

LeetCode 402 - Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
http://www.voidcn.com/blog/yeqiuzs/article/p-6204756.html
public String removeKdigits(String num, int k) {
        Stack<Integer> stack = new Stack<Integer>();
        if (num.length() == 0 || num.length() <= k)
            return "0";

        for (int i = 0; i < num.length(); i++) {
            int cur = num.charAt(i) - '0';
            while (!stack.isEmpty() && cur < stack.peek()
                    && num.length() - i - 1 >= (num.length() - k) - stack.size()) {
                stack.pop();
            }
            if (stack.size()<num.length()-k)
                stack.push(cur);
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty())
            res.insert(0, stack.pop());

        while (res.length() > 0 && res.charAt(0) == '0')
            res.deleteCharAt(0);

        if (res.length() == 0)
            return "0";
        return res.toString();
    }


X. It should be intuitive for questions like parentheses
LeetCode 385 - Mini Parser
http://www.programcreek.com/2014/08/leetcode-mini-parser-java/
public NestedInteger deserialize(String s) {
 
    Stack<NestedInteger> stack = new Stack<NestedInteger>();
    String temp = "";
 
    for(char c: s.toCharArray()){
        switch(c){
            case '[':
                stack.push(new NestedInteger()); //start a new NI
                break;
 
            case ']':
                if(!temp.equals("")){
                    stack.peek().add(new NestedInteger(Integer.parseInt(temp))); //add NI to parent
                    temp="";
                }
 
                NestedInteger top = stack.pop();
                if(!stack.empty()){
                    stack.peek().add(top);
                }else{
                    return top;
                }
 
                break;
 
            case ',':
                if(!temp.equals("")){
                    stack.peek().add(new NestedInteger(Integer.parseInt(temp)));//add NI to parent
                    temp="";
                }
 
                break;
 
            default:
                temp += c;
        }
    }
 
    if(!temp.equals("")){
        return new NestedInteger(Integer.parseInt(temp));
    }
 
    return null;
}

X. Recursive version
https://discuss.leetcode.com/topic/54277/short-java-recursive-solution
https://discuss.leetcode.com/topic/54407/java-recursive-solution-one-scan-clean-easy-to-understand
    public NestedInteger deserialize(String s) {
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        NestedInteger result = new NestedInteger();
        helper(s, 1, result);
        return result;
    }

    private int helper(String s, int idx, NestedInteger parent) {
        int l = idx, r = idx;
        while (r < s.length()) {
            String num = s.substring(l, r);
            if (s.charAt(r) == '[') {
                NestedInteger child = new NestedInteger();
                parent.add(child);
                r = helper(s, r + 1, child);
                l = r;
            } else if (s.charAt(r) == ']') {
                if (!num.isEmpty()) parent.add(new NestedInteger(Integer.valueOf(num)));
                return r + 1;
            } else if (s.charAt(r) == ',') {
                if (!num.isEmpty()) parent.add(new NestedInteger(Integer.valueOf(num)));
                r++;
                l = r;
            } else {
                r++;
            }
        }
        return s.length();
    }


LeetCode 388 - Longest Absolute File Path
Suppose we abstract our file system by a string in the following manner:
The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
dir
    subdir1
    subdir2
        file.ext


The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.
https://discuss.leetcode.com/topic/55561/two-different-solutions-in-java-using-stack-and-hashmap
    public int lengthLongestPath(String input) {
        ArrayDeque stack = new ArrayDeque<>();
        int result = 0;
        for (String s : input.split("\n")) {
            int level = s.lastIndexOf("\t") + 1;
            while (stack.size() != level) {
                stack.pop();
            }
            int len = s.length() - level; //s.substring(level).length();
            if (stack.isEmpty()) {
                stack.push(len);
            } else {
                stack.push(stack.peek() + len + 1);
            }
            if (s.contains(".")) {
                result = Math.max(result, stack.peek());
            }
        }
        return result;
    }
X. Using HashMap
    public int lengthLongestPath2(String input) {
        HashMap hashMap = new HashMap<>();
        hashMap.put(0, 0);
        int result = 0;
        for (String s : input.split("\n")) {
            int level = s.lastIndexOf("\t") + 1;
            int len = s.length() - level; //s.substring(level).length();
            if (s.contains(".")) {
                result = Math.max(result, hashMap.get(level) + len);
            } else {
                hashMap.put(level + 1, hashMap.get(level) + len + 1);
            }
        }
        return result;
    }

X. Stack itself
LeetCode 456 - 132 Pattern
- Use Stack
- Use Binary Search Tree

LeetCode 402 - Remove K Digits
remove k digits from the number so that the new number is the smallest possible.
while(k>0 && !stack.isEmpty() && stack.peek()>num.charAt(i)){
    stack.pop();
    k--;
}

LeetCode 439 - Ternary Expression Parser
Input: "F?1:T?4:5" Output: "4"
Input: "T?T?F:5:3" Output: "F"
- Stack: Iterate the expression from tail, whenever encounter a character before '?', calculate the right value and push back to stack.
- Recursion
This : has the property that the number of ? ahead of this : should equals the number of :, similar to the case of ( and ).
- Build express tree

Expression
- getPriority, isOperator, compute
LeetCode – Evaluate Reverse Polish Notation
Lintcode - Expression Tree Build
  public ExpressionTreeNode build(String[] expression) {
    if (expression == null || expression.length == 0) {
      return null;
    }
    Stack numStack = new Stack<>();
    Stack opStack = new Stack<>();
    for (String token : expression) {
      if (isNumber(token)) {
        numStack.push(new ExpressionTreeNode(token));
      } else if (token.equals("(")) {
        opStack.push(token);
      } else if (token.equals(")")) {
        while (!opStack.peek().equals("(")) {
          numStack.push(buildNode(numStack.pop(), numStack.pop(), opStack.pop()));
        }
        opStack.pop();
      } else {
        while (!opStack.isEmpty() && getPriority(opStack.peek()) >= getPriority(token)) {
          numStack.push(buildNode(numStack.pop(), numStack.pop(), opStack.pop()));
        }
        opStack.push(token);
      }
    }
    while (!opStack.isEmpty()) {
      numStack.push(buildNode(numStack.pop(), numStack.pop(), opStack.pop()));
    }
    return numStack.isEmpty() ? null : numStack.pop();
  }
  private int getPriority(String op) {
    if (op.equals("(")) {
      return 0;
    } else if (op.equals("+") || op.equals("-")) {
      return 1;
    } else {
      return 2;
    }
  }
Convert Expression to Reverse Polish Notation
Convert Expression to Polish Notation
- scan from right to left

LeetCode 224 - Basic Calculator
- Using one stack: store prevResult and preSign when scan (
LeetCode 227 - Basic Calculator II

Posted by at
Labels: ,

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)