LeetCode101: 456. 132 Pattern
tags: Monotonic Stack,LeetCode101,Tricky We travel the numbers in the reverse order: Use a mono-increasing stack to find the largest number(3 in the 132 pattern), the value popped from stack is the second large number(2 in the 132 pattern), if any value less than the second large number, returns true. // Note: // // - subsequence is not contiguous, is i < j < k, not i + 1 = j, j + 1 = k // class Solution { public: bool find132pattern(vector<int>& nums) { int K = INT_MIN; stack<int> mst; // mono-increasing stack for (int i = nums.size() - 1; i >= 0; i--) { if (nums[i] < K) { return true; } while (!mst.empty() && mst.top() < nums[i]) { K = mst.top(); mst.pop(); } mst.push(nums[i]); } return false; } };