LeetCode 456 132 Pattern

LeetCode

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-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].

Constraints:

n == nums.length 1 <= n <= 2 * 10<sup>5</sup>
* -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

题目大意：

给定一个数组，找一个3个数的序列，满足后两个数交换后是有序的。

解题思路：

此题较难理解，首先要拆分为三个条件：中间的数大于两边的，左边的数小于右边的
num[i] < num[j]
num[k] < num[j]
num[i] < num[k]
这3个条件要贯彻在代码中

第一方法：暴力法是三重循环遍历i, j, k满足上述三个条件，复杂度为O(n^3)
第二方法：贪婪法。这题是寻找有或者无，所以不需要直到具体答案而且i对应的数值越小越好容易找到答案，因为这样nums[i], nums[j]之间的区间越大，越容易找到k。我们把nums[i]变成min_i, 这样遍历j的时候，顺便可以求min_i同时保证j和k的值都大于min_i，减少了一轮循环复杂度为O(n^2)
第三方法：递减栈。由第二方法，我们可以把min_i值都存起来，这是一个mins[i]为以i为结尾的子数组的最小值，很容易满足num[i] < num[k]和num[i] < num[j]。难点在要找一个比nums[j]小的数就满足num[k] < num[j]，容易想到LeetCode 503 Next Greater Element II里面的递减栈，不过那题是求下一个比自己大的数，所以要反着做，从数组从后向前遍历。

解题步骤：

1. Populate mins数组
2. 递减栈的实现分别要满足上述三个条件。mins[j], num[j], stack[-1]分别代表i，j和k

注意事项：

1. 输入只有一个数的时候

Python代码：

def find132pattern(self, nums: List[int]) -> bool:
	mins = [nums[0]]
	for i in range(1, len(nums)):
		mins.append(min(nums[i], mins[i-1]))
	stack = []
	for j in range(len(nums) - 1, -1, -1):
		if nums[j] <= mins[j]: # num[i] < num[j]
			continue
		while stack and stack[-1] <= mins[j]: # num[i] < num[k] 
			stack.pop()
		if stack and stack[-1] < nums[j]: # num[k] < num[j] 
			return True
		stack.append(nums[j])
	return False

算法分析：

时间复杂度为O(n)，空间复杂度O(n)