C++ Explanation Using Stack


  • 0
    X

    We use a Monotonic Stack

    when we scan the sequence, we have 2 options:

    1. put it to the left, if current number is less than the above number
      may violate lower bound
      insert 1 and 3 is different
    2
     \
      5
     /
    (1)
    (3)
    
    1. put it to the right, if current number is larger than the above number
      insert 2 and 4 is different
      we increase largest_seen as little as possible to accommodate nodes as many as possible
       3
      / \
      1  (4)
       \
       (2)
    
    1. no above number, i.e. stack is empty
      It is definitely safe to push current number to the stack

    Notice: the above number is at the top of the stack.

    class Solution {
    public:
        bool verifyPreorder(vector<int> &preorder) {
            stack<int> s;
            long largest_seen = LONG_MIN;
    
            for (const int &num : preorder) {
                if (!s.empty() && num < s.top()) { // put it to the left
                    if (num <= largest_seen) {
                        return false;
                    }
                } else {  // put it to the right
                    while (!s.empty() && num >= s.top()) {
                        largest_seen = s.top();  // num is at right of it
                        s.pop();
                    }
                }
                s.push(num);
            }
            return true;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.