[leetcode] 456. 132 Pattern (Medium)

对一个三个元素以上的数组，如果存在1-3-2模式的组合，则返回true。

1-3-2模式就是值的排序是i<k<j但是下标排序是i<j<k。

解法一：

硬解，利用一个变量存储是否找到了较大值和较小值，因为是1-3-2，所以从后往前遍历才能找到较当前值更大和更小的值。

Runtime: 648 ms, faster than 12.76% of C++ online submissions for 132 Pattern.

class Solution
{
public:bool find132pattern(vector<int> &nums){if (nums.size() < 3)return false;int a = 0;int times = 0;for (int i = nums.size()-1; i > 1; --i){a = nums[i];times=0;for (int j = i - 1; j >=0; --j){if (nums[j] > a && times == 0)times++;if (nums[j] < a && times == 1)times++;}if(times==2)return true;}return false;}
};

解法二：

利用栈，这里涉及到一个栈排序的知识，看一下有助于理解。

class Solution
{
public:bool find132pattern(vector<int> &nums){stack<int> s;int prev = INT_MIN;for (int i = nums.size() - 1; i >= 0; i--){while (!s.empty() && s.top() < nums[i]){if (prev > s.top())return true;prev = s.top();s.pop();}s.push(nums[i]);}return !s.empty() && prev > s.top();}
};