|
| 1 | +/* |
| 2 | + Given nums, return true if there is a 132 pattern where |
| 3 | + num[i] < nums[k] < nums[j] for i < j < k |
| 4 | +
|
| 5 | + Use a monotonically decreasing stack to store a pair |
| 6 | + {candidate nums[j], candidate nums[i]} where |
| 7 | + candidate nums[i] is the minimum number in nums before j |
| 8 | +
|
| 9 | + Traverse nums. |
| 10 | + Pop the stack while n >= candidate nums[j] at the top of the stack (n is a better candidate than those) |
| 11 | + Then, if stack not empty, check if 132 patter if found --> return True |
| 12 | + Else, add the current num as a candidate nums[j] with the current min as the candidate nums[i] then update current min |
| 13 | +*/ |
| 14 | +classSolution { |
| 15 | +public: |
| 16 | +boolfind132pattern(vector<int>& nums) { |
| 17 | + stack<pair<int,int>> s; |
| 18 | +int curMin = nums[0]; |
| 19 | + |
| 20 | +for(auto & n : nums){ |
| 21 | +// pop all values in stack that have nums[j] candidate <= n |
| 22 | +while(!s.empty() && s.top().first <= n){ |
| 23 | + s.pop(); |
| 24 | + } |
| 25 | +// if stack not empty, check if we found 132 pattern |
| 26 | +if(!s.empty() && s.top().second < n)returntrue; |
| 27 | +else{ |
| 28 | +// add n to stack and update curMin |
| 29 | + s.push({n, curMin}); |
| 30 | + curMin =min(curMin, n); |
| 31 | + } |
| 32 | + } |
| 33 | +returnfalse; |
| 34 | + } |
| 35 | +}; |