255. Verify Preorder Sequence in Binary Search Tree

I was trying divide and conquer solution as following but got TLE.

1:  class Solution {  
2:  public:  
3:    bool verifyPreorder(vector<int>& preorder) {  
4:      if (preorder.empty()) return true;  
5:      return helper(preorder, 0, preorder.size()-1);  
6:    }  
7:    bool helper(vector<int> &preorder, int s, int e) {  
8:      if (s >= e) return true;  
9:      int pivot = preorder[s];  
10:      int bigger = -1;  
11:      for (int i = s+1; i <= e; i++) {  
12:        if (bigger == -1 && preorder[i] > pivot) bigger = i;  
13:        if (bigger != -1 && preorder[i] < pivot) return false;  
14:      }  
15:      if (bigger == -1) {  
16:        return helper(preorder, s+1, e);  
17:      } else {  
18:        return helper(preorder, s+1, bigger-1) && helper(preorder, bigger, e);  
19:      }  
20:    }  
21:  };  

Then I have to follow the top rated solution which uses stack. The idea is to traverse the list and use a stack to store all predecessors. As long as the stack's top node is less than the current list node, we can assume that the current list node is a predecessor and push it to the stack. Once we meet a node that is larger than the top node, we know we are going to enter the right subtree and we need to pop out all the predecessors that are less than current list node but keep the last predecessor. And then we push the current list node into stack and we enters the right subtree. Note for the right subtree, all the node must be larger than the last predecessor, if not then we conclude that it is an invalid preorder sequence in BST.

1:  class Solution {  
2:  public:  
3:    bool verifyPreorder(vector<int>& preorder) {  
4:      if (preorder.size() < 2) return true;  
5:      stack<int> stk;  
6:      stk.push(preorder[0]);  
7:      int last = INT_MIN;  
8:      for (int i = 1; i < preorder.size(); i++) {  
9:        if (stk.empty() || preorder[i] < stk.top()) {  
10:          if (preorder[i] < last) return false;  
11:          stk.push(preorder[i]);  
12:        } else {  
13:          while (!stk.empty() && stk.top() < preorder[i]) {  
14:            last = stk.top();  
15:            stk.pop();  
16:          }  
17:          stk.push(preorder[i]);  
18:        }  
19:      }  
20:      return true;  
21:    }  
22:  };