[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();} };