stack （栈）

Tree
173 Binary Search Tree Iterator
    This problem is actually Iterative inOrder traversal
     maintain a  pushLeft function and a data member stack<TreeNode*> st. Call pushLeft in
     the constructor BSTIterator. And hasNext() is just check the stack is not NULL. next() is
     just visit st.top() element. But in order to visit the right child, we have to pushLeft(p->right)
    before return p->val. It is a good idea to use pushLeft function in inOrder Traversal.


150 Evaluate Reverse Polish Notation
Keep push the numbers onto the stack until see an operator, then pop two elements from stack top and do num2 op num1 and push the result back to the stack. Keep doing for all the strings in the input vector array. In the end return the stack top element, which is the final result calculated.


682

Use stack to solve the problem, since all the operation are on the top two elements of the stack.
 For loop each string str in the input ops vector. Do the following:
 if  str == "C" pop the stack
 else if str == "+" pop the the top two elements and get the sum, push back the two elements in the reverse order of pop and also push the sum on the stack
else if str == "D" push the top * 2 on the stack
else  push the value stoi(str) to the stack
Loop the stack and accumulate the sum.

844  Backspace String Compare
(1) For both the string S and T do the following (2)
(2) For loop each char c in the string if  c is not equal to '#' push on to the stack. Otherwise if the the stack is not empty pop the stack top element.
(3) Compare the remaining elements on the stack to see whether S is equal to T.
 Note: here we can use stack<char> or vector<char>, the later one is easier for comparing two arrays.

232  Implement Queue using Stacks
Use two stacks to mimic Queue
Naive:
(1) push : always push to the first stack
(2) pop : transfer all the elements in stack 1 to stack 2 and pop from the top of stack 2 and then transfer back to stack 1.
(3) top : similar idea as pop, except, we don't need to pop from stack 2, just access it.
(4) empty: check whether stack 1 is empty.

Better:
(1) push : always push to the first stack
(2) pop : If stack 2 is not empty, pop from stack 2. Otherwise transfer all the elements in stack 1 to stack 2 and pop from the top of stack 2.
(3) top : If stack 2 is not empty, access top of stack 2. Otherwise transfer all the elements in stack 1 to stack 2 and access from the top of stack 2.
(4) empty: check whether both stack 1 and stack 2 are empty.

225 Implement Stack using Queues 
Use two queues to mimic stack
Naive:
(1) push : always push to the first queue
(2) pop : transfer the first n - 1 elements in queue 1 to queue 2 and pop the last element in queue 1.
      And then swap queue 1 and queue 2 to avoid copying.
(3) top : transfer all the elements in queue 1 to queue 2 and save the last element in queue 1,  then swap queue 1 and queue 2 to avoid copying, and return the save last element 1 in queue 1.
(4) empty: check whether queue 1 is empty.

Better:
Just need one queue to mimic stack
(1) push : always push to the back of queue. But left shift all the elements in front of it to its back. So the newly inserted element is always in front of the queue.
(2) pop : pop from front of queue.
(3) top : return front() of queue.
(4) empty: check whether the queue is empty.


20
  For loop each char c in the input string. Do the following:
  case '{' '[' '('  push into the stack
  case '}' ']' ')' check whether the stack is not empty and the top element is the matching left bracket.
                     if not return false.
After the loop, check whether  the stack is empty, if so the parentheses string is valid, otherwise invalid.


For loop each asteroid in the array do the following
(1) If the stack is empty()
      (1.1) if asteroid > 0, push it onto the stack
       (1.2) else push it into the result vector array (it survives) 
(2)  else if the stack is not empty()
   (2.1) if asteroid > 0, push it onto the stack
   (2.2)  else check the stack top element and the current asteroid size, the bigger one survives,
            if the current one survives, we still have to pop the stack and check the next one.
(3) In the end, reverse the elements in the stack and push it into the result array in reversed order.

739. Daily Temperatures  
Define a stack, and initialize the N value of result array to all zero
(1) Loop the temperature array backward.  Use the stack to save the temperature index looped.
(2) While the stack is not empty and the current temperature is greater than the temperature at stack top index, pop the stack.
(3) set result array value at the current temperature index j to 0 if the stack is empty. Otherwise to stack top value minus j.
(4) push j to the stack
(5) return the result array.


71 Simplify Path

Define a stack of string. Use getline of stringstream to split the path string. skip "." and "", when meet ".." if the stack is not empty() pop() stack,  for all other  cases push() stack. Finally, for loop the stack elements to construct the simplified path.

 


Second time
================================================================
 496 Next Greater Element I   
O(N) time and O(N) space stack + hash map algorithm.
Key observation:
Suppose we have a decreasing sequence followed by a greater number
For example [5, 4, 3, 2, 1, 6] then the greater number 6 is the next greater element for all previous numbers in the sequence

We use a stack to keep a decreasing sub-sequence, whenever we see a number x greater than stack.top() we pop all elements less than x and for all the popped ones, their next greater element is x
For example [9, 8, 7, 3, 2, 1, 6]
The stack will first contain [9, 8, 7, 3, 2, 1] and then we see 6 which is greater than 1 so we pop 1 2 3 whose next greater element should be 6

503Next Greater Element II   
O(N) time and O(n) space, O(1) extra space stack algorithm
 The time is O(n) is we push at most 2*N elements into the stack at most
The second way is to use a stack to facilitate the look up. First we put all indexes into the stack, smaller index on the top. Then we start from end of the array look for the first element (index) in the stack which is greater than the current one. That one is guaranteed to be the Next Greater Element. Then put the current element (index) into the stack.



636
  Use a stack to parse the log while looping each log in the input logs.
  (1) When see a start log, split each part and construct a log node and push onto the stack.
  (2) When see a end log, also split each part and construct a log node, using the matching log on top of the stack to calculate the duration for this function. Also if there is an enclosing caller, we need to subtract the total duration time from it.
 (3) return the result array.



341
Similar to 385 mini Parser
The same idea as a DFS, the only tricky part probably is you have to find a value node to claim there is next. And to do that, you have to look through all the nodes in the worst case in the entire graph. So you just keep going until you find a value node; if you can't, there is no next.




394  Decode String

DFS Recursive
Pass a reference of the current char index (initialized to 0) and the input s to a helper function. In which we define a result string. While the  index is less than the  input string size and not the last char ']', if the current char is a digit calculate the repeated value in another loop, recursively call the DFS helper function to calculate the embedded string and return a temp string, add repeated copy of the temp string to the result . else the current char is a letter. Add the letter to the result. Finally, return the result string.

Non-recursive Stack:
The idea is to use two stacks to process the input string.
One characters stack char and one number stack num.
For loop each char c in the input string s do the following:
(1) case numbers: num = num * 10 + (c - '0');
(2) case letters:     res.push_back(c);
(3) case '['             chars.push(res), nums.push(num), res.clear(), num = 0;
(4) case ']'             get the top element number n from nums stack, and add n copies of res to a tmp string. get the top element str from top of chars stack. and add it before tmp string. assign tmp to res.
pop both the number and char stacks.

return res string in the end.


 385. Mini Parser
Recursive:
Using istringstream  to split the input separated by ',' and '[]'. If the current part is a integer
return NestInteger(integer). Otherwise create a list and DFS recursively add the  deserialize result and return the list.
 Non-Recursive Stack:
Uses a stack to record the NestedInteger's.
At the very beginning, an empty NestedInteger is placed in the stack. This NestedInteger will be regarded as a list that holds one but only one NestedInteger, which will be returned in the end.
Logic: When encountering '[', the stack has one more element. When encountering ']', the stack has one less element.

Complexities:
    Time: O(n)
    Space: worse-case O(n) (worse case: [1,[2,[3,[....[n-1,[n]]]....])

Tree

94 Binary Tree Inorder Traversal
      (a)  Recursive:  DFS(root->left, res), res.push_back(root->val), DFS(root->right, res);
      (b) Iterative:  (b.1) Use a stack st to do this. Define p and initialize it to root. While p is not NULL and the stack st is not empty(), do the following.  (b.2) while p is not NULL, keep push p into the stack and let p = p->left. (b.3) after b.2, check if the stack is not empty. If so, visit the top element and pop it and let p = p->right.

 144  Binary Tree Preorder Traversal
         Iterative: Using a stack, push the root into stack first. While the stack is not empty. pop and
         visit the top node. If the right (note here we push the right before left, so when pop, we will
        visit left before right) child is not NULL,  push the right child into stack. If the left child is
        not NULL, push the left into stack. Keep doing this until all the nodes are visited.

103 Binary Tree Zigzag Level Order Traversal
 Stack solution:
 Use two stacks curLevel stack and nextLevel stack to traverse the tree. Since we need to output the nodes in normal order for odd level and reverse order for even level, we only need a bool flag (like zigzag).
(1) Push the root into the curLevel stack before the loop.
(2) while curLevel is not empty, repeat the following.
    (2.1) Define nextLevel stack, and level vector array to save this level nodes value
    (2.2) while curLevel is not empty()
           pop the top element. Depends on whether zigzag is true or false do the following:
              true : push the left and then push the right
             false: push the right and then push the left
    (2.3) flip zigZag flag, push the level to the result vector of vector array
             copy the nextLevel stack to the curLevel stack to do the next loop (go to (2))
  





(1) Use stringstream + getline with customized seperator ',' to split the string into nodes
(2) Define a stack and for loop each string in the nodes array. Do the following:
 while node equal to "#" and stack not empty and the top stack element is also equal to "#"
 pop top element (matching "#"), if stack is empty, meaning invalid string, return false.
 Otherwise it is valid currently, pop the element that has two "#" children (either added
 or original). Push the node onto the stack after the while loop
(3) check whether the only left string on the stack is "#" in the end

O(N) time and O(N) space.

 456 132 Pattern   
  1. Have a stack, each time we store a new number, we first pop out all numbers that are smaller than that number. The numbers that are popped out becomes candidate for s3.
  2. We keep track of the maximum of such s3 (which is always the most recently popped number from the stack).
  3. Once we encounter any number smaller than s3, we know we found a valid sequence since s1 < s3 and we know s2 > s3
RUNTIME: Each item is pushed and popped once at most, the time complexity is therefore O(n).

402  Remove K Digits
 
        Keep track of how many characters we can remove
        if the previous character in stk is larger than the current one
        then removing it will always get a smaller number
        but we can only do so when k is larger than 0

42 Trapping Rain Water  （接雨水）

这题最关键的是想清楚如何使用单调栈表示凹槽。可以这样思考。如果我们维护一个单调降的栈，当新的元素小于等于栈顶元素时直接入栈。当前元素严格大于栈顶元素时，我们就出栈。这时候出栈表示什么意思呢？意味着我们找到了一个可能的凹槽。我们先把当前栈顶元素出栈（这个元素凹槽的中间底部），这时候新的栈顶就是凹槽的左边界下标left （height[left]即为左边界高度），而当前的元素height[i] 就是凹槽的右边界下标right（height[right]即为右边界高度）。左右边界取最小值然后减去中间凹槽高度就是水柱的高度，水柱的长度就是i - left - 1 (或者right - left）就是水柱的长度。水柱总水量就是水柱长度乘以水柱的高度。把它累计到最后的总水量里面。如此循环完毕每一个小方块，就累计得到最后的总雨量。

具体代码如下
int trap(vector<int>& height) {
        stack<int> monoStack;
        int res = 0;
        for (int i = 0; i < height.size(); i++) {
            // Found a possible rut/groove (only confirmed if leftHeight > middleHeight)
            while (!monoStack.empty() && height[i] > height[monoStack.top()]) {
                auto middleHeight = monoStack.top();
                monoStack.pop();
                if (monoStack.empty()) {
                    break; // leftHeight <= middleHeight, cannot hold water
                }

                int waterWidth = i - monoStack.top() - 1;
                int waterHeight = min(height[monoStack.top()] /* rut left height */,
                height[i] /* rut right height */) - height[middleHeight];
                int waterAmount = waterHeight * waterWidth;
                res += waterAmount;
            }
            monoStack.push(i);
        }

        return res;       
    }
 




Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

Array Part2

Two pointers 977 Squares of a Sorted Array      We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction. Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique. 11 Container With Most Water      O(N) time and O(1) space, since better candidadates must use the taller line of l and r therefore we can use two pointer keep moving towards each other until they meet. Always abandon the shorter line while moving. 80 Remove Duplicates from Sorted Array II      tail = 0; for (int i = 0;  i < nums.size(); i++)           if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                 nums[tail++] = nums...
Read more

Two pointers (Part 1)

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...
Read more