LeetCode 132 Pattern Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list. Note: n will be less than 15,000. Example 1:
Input: [1, 2, 3, 4] Output: False Explanation: There is no 132 pattern in the sequence.Example 2:
Input: [3, 1, 4, 2] Output: True Explanation: There is a 132 pattern in the sequence: [1, 4, 2].Example 3:
Input: [-1, 3, 2, 0] Output: True Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
给定一个数组，问数组中是否存在132这样的子序列。132是指i<j<k，但a[i]<a[k]<a[j]的形式，132就是这样一个例子，中间最大，右边次之，左边最小。 解法1。朴素解法，直接查找是否存在这样的i,j,k。首先找i，即满足a[i]<a[i+1]这样的i。然后找j，我们希望a[j]越大越好，这样的话，才可能找到a[k]<a[j]的k，所以a[j]<a[j+1]时，j++，因为前面有更大的a[j]，照样满足a[i]<a[j]，还可能更容易找到小于a[j]的a[k]。当确定i,j之后，a[k]就在j后面不断找在a[i]和a[j]之间的数。 代码如下： [cpp] class Solution { public: bool find132pattern(vector<int>& nums) { int i = 0, j = 0, k = 0, n = nums.size(); while (i < n) { while (i < n – 1 && nums[i] >= nums[i + 1])++i; j = i + 1; while (j < n – 1 && nums[j] <= nums[j + 1])++j; k = j + 1; while (k < n) { if (nums[k] > nums[i] && nums[k] < nums[j])return true; ++k; } ++i; } return false; } }; [/cpp] 本代码提交AC，用时299MS。 解法2。使用栈。从数组末尾往前找，我们希望a[j]越大越好，而a[k]最好是次大的，这样a[i]就更容易小于a[k]了。定义一个变量third表示132模式中的第三个数，就是132中的2。初始时令third=INT_MIN。定义一个堆栈stk保存比third大的所有数，如果nums[i]小于third，表示找到了第一个数1，返回true。如果nums[i]大于stk栈顶，表示找到了更大的数，则把stk中的数给third，表示third保存的是次大的数，然后把nums[i]压入stk。 代码如下： [cpp] class Solution { public: bool find132pattern(vector<int>& nums) { stack<int> stk; int third = INT_MIN; for (int i = nums.size() – 1; i >= 0; –i) { if (nums[i] < third)return true; else { while (!stk.empty() && nums[i] > stk.top()) { third = stk.top(); stk.pop(); } stk.push(nums[i]); } } return false; } }; [/cpp] 本代码提交AC，用时23MS，快了不少。]]>