456. 132 模式

🟠   🔖  栈 数组 二分查找 有序集合 单调栈  🔗 力扣 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 a132 pattern in nums , otherwise, returnfalse .

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^5
• -10^9 <= nums[i] <= 10^9

题目大意

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

示例 1：

输入： nums = [1,2,3,4]

输出： false

解释： 序列中不存在 132 模式的子序列。

示例 2：

输入： nums = [3,1,4,2]

输出： true

解释： 序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

示例 3：

输入： nums = [-1,3,2,0]

输出： true

解释： 序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

提示：

• n == nums.length
• 1 <= n <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

解题思路

目标：找到一个满足 nums[i] < nums[k] < nums[j] (i < j < k) 的 132 模式。

我们可以利用 单调栈 来高效地维护 nums[j]（132 模式中的第二个元素），从而在 O(n) 时间复杂度内解决问题。

1. 倒序遍历 nums

   • nums[k] 必须出现在 nums[j] 之后，因此倒序遍历 nums，先找到 nums[j]，从而确保 nums[i] < nums[k] < nums[j]。

2. 使用单调递减栈维护 nums[j]

   • stack 存储可能的 nums[j]，并保持单调递减（栈顶元素最大）。

3. 使用 third 存储可能的 nums[k]

   • 当 stack 不为空，且 stack 栈顶元素小于当前 nums[i]，说明 stack.pop() 是一个合适的 nums[k]，将 third = stack.pop() 进行更新。
   • 然后将当前 nums[i] 放入栈顶，这样就确保了 nums[k] < nums[j]。

4. 判断 nums[i] 是否满足 nums[i] < third

   • 如果 nums[i] < third，说明找到了 132 模式，直接返回 true。

复杂度分析

• 时间复杂度：O(n)，每个元素最多入栈、出栈一次，总共 O(n)。
• 空间复杂度：O(n)，最坏情况下栈存储 n 个元素。

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function (nums) {
	let stack = [];
	let third = -Infinity;
	for (let i = nums.length - 1; i >= 0; i--) {
		if (nums[i] < third) return true;
		while (stack.length && stack[stack.length - 1] < nums[i]) {
			third = stack.pop();
		}
		stack.push(nums[i]);
	}
	return false;
};