LeetCode 456. 132 Pattern

问题描述

给一组数，判断这组数中是否含有132 pattern。

132 pattern： i < j < k，且 a_i< a_k < a_j

第一种解法

使用栈来保存候选的子区间，不断地判断新元素是否落在栈顶的区间内，这其中需要一些判断。

 1 class Solution
 2 {
 3 public:
 4     bool find132pattern(vector<int>& nums)
 5     {
 6         int n = nums.size();
 7         stack<pair<int,int>> minmax;
 8         for (int i = 0; i < n; i++)
 9         {
10             if (minmax.empty() || nums[i] < minmax.top().first)
11                 minmax.push(pair<int, int>(nums[i], nums[i]));
12             else if (nums[i] > minmax.top().first)
13             {
14                 pair<int, int> cur = minmax.top();                
15                 minmax.pop();                
16                 if (nums[i] < cur.second)
17                     return true;                
18                 else
19                 {
20                     cur.second = nums[i];
21                     // 如果当前元素已经比stack的top的max还大，那么top已经没有存在的意义了,因为当cur的min一定是小于top的min的，是包含关系
22                     while (!minmax.empty() && nums[i] > minmax.top().second) 
23                         minmax.pop();
24                     // 判断当前元素是否在top的区间中
25                     if (!minmax.empty() && nums[i] > minmax.top().first)
26                         return true;
27                 }
28                 minmax.push(cur);
29             }
30         }
31         return false;
32     }
33 };

第二种解法

设132分别为 s1, s2, s3，且满足， s1<s3<s2。

则这个方法是每次找到符合条件的s3，即右侧有比它小的元素，然后判断下一个数是否比s3小，如果存在，则返回true。

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