Stack Summary

I. Stack Basics
20. Valid Parentheses
42. Trapping Rain Water
71. Simplify Path
150. Evaluate Reverse Polish Notation ()
224. Basic Calculator ()
316. Remove Duplicate Letters ()

II. harder
84. Largest Rectangle in Histogram ()
85. Maximal Rectangle (*)

III, tree
94 Binary Tree Inorder Traversal 38.5% Medium
103 Binary Tree Zigzag Level Order Traversal 27.8% Medium
144 Binary Tree Preorder Traversal 38.6% Medium
145 Binary Tree Postorder Traversal 34.4% Hard
173 Binary Search Tree Iterator 32.9% Medium
255 Verify Preorder Sequence in Binary Search Tree 35.7% Medium
272 Closest Binary Search Tree Value II 31.1% Hard
331 Verify Preorder Serialization of a Binary Tree

IV, design
155. Min Stack
239. Sliding Window Maximum – similar to min stack ()
225. Implement Stack using Queues ()
232. Implement Queue using Stacks ()

Stack

20 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.

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack, lookup = [], {"(": ")", "{": "}", "[": "]"}
        for parenthese in s:
            if parenthese in lookup:
                stack.append(parenthese)
            elif len(stack) == 0 or lookup[stack.pop()] != parenthese:
                return False
        return len(stack) == 0

42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        area=0
        maxl,maxr=[],[]
        tmp=0
        for i in range(len(height)):
            if height[i]>tmp: tmp=height[i]
            maxl.append(tmp)
        tmp=0
        for i in range(len(height)-1,-1,-1):
            if height[i]>tmp: tmp=height[i]
            maxr.append(tmp)
        area=0
        for i in range(1,len(height)-1):
            minh=min(maxl[i],maxr[len(height)-i-1])-height[i]
            area+=minh if minh>0 else 0
        return area

71. Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = “/home/”, => “/home”
path = “/a/./b/../../c/”, => “/c”

Corner Cases:
Did you consider the case where path = “/../”?
In this case, you should return “/”.
Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”.
In this case, you should ignore redundant slashes and return “/home/foo”.

class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """        
        stack, tokens = [], path.split("/")
        for token in tokens:
            if token == ".." and stack:
                stack.pop()
            elif token != ".." and token != "." and token:
                stack.append(token)
        return "/" + "/".join(stack)