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]之间的数。

代码如下:

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;
	}
};

本代码提交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。

代码如下:

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;
	}
};

本代码提交AC,用时23MS,快了不少。

Leave a Reply

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