LeetCode 132 Pattern

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,快了不少。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *