leetcode456 132 模式

思路1：

枚举3。

实现1：

 1 class Solution
 2 {
 3 public:
 4     bool find132pattern(vector<int>& nums)
 5     {
 6         int n = nums.size();
 7         if (n < 3) return false;
 8         multiset<int> s;
 9         for (int i = 1; i < n; i++) s.insert(nums[i]);
10         int minn = nums[0]; 
11         for (int i = 1; i < n; i++)
12         {
13             auto it = s.upper_bound(minn);     
14             if (*it > minn and *it < nums[i]) return true;
15             minn = min(minn, nums[i]);
16             it = s.find(nums[i]);
17             s.erase(it);
18         }
19         return false;
20     }
21 };

思路2：

枚举1。

实现2：

 1 class Solution
 2 {
 3 public:
 4     bool find132pattern(vector<int>& nums)
 5     {
 6         int n = nums.size();
 7         if (n < 3) return false;
 8         stack<int> st;
 9         int maxn = -1e9;
10         for (int i = n - 1; i >= 0; i--)
11         {
12             if (nums[i] < maxn) return true;
13             while (!st.empty() and nums[i] > st.top())
14             {
15                 maxn = max(maxn, st.top());
16                 st.pop();
17             }
18             st.push(nums[i]);
19         }
20         return false;
21     }
22 };