132 模式
难度:
标签:
题目描述
给你一个整数数组 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.length1 <= n <= 2 * 105-109 <= nums[i] <= 109
代码结果
运行时间: 82 ms, 内存: 32.7 MB
/*
* 使用Java Stream的方式实现132模式。
*
* 思路：
* 1. 我们先用IntStream.range从0到nums.length创建一个索引流，然后用mapToObj创建一个包含索引和值的流。
* 2. 我们先筛选出所有满足 nums[i] < nums[k] < nums[j] 且 i < j < k 的子序列
* 3. 如果找到任何一个符合的子序列就返回true，否则返回false。
*/
import java.util.stream.IntStream;
import java.util.stream.Stream;
import java.util.Optional;
public class Solution {
public boolean find132pattern(int[] nums) {
return IntStream.range(0, nums.length - 2)
.boxed()
.flatMap(i -> IntStream.range(i + 1, nums.length - 1)
.boxed()
.flatMap(j -> IntStream.range(j + 1, nums.length)
.mapToObj(k -> new int[]{nums[i], nums[j], nums[k]})))
.anyMatch(arr -> arr[0] < arr[2] && arr[2] < arr[1]);
}
}解释
方法:
这个题解使用单调栈的思路来解决问题。从后往前遍历数组，维护一个逆向的不严格递减栈，栈顶元素代表答案中的中间数。同时用一个变量 right 记录遍历过程中遇到的最大的右边界。如果当前元素小于 right，说明找到了一个 132 模式，直接返回 True。否则，将栈中小于当前元素的数都弹出，并更新 right 为弹出的元素中的最大值，然后将当前元素压入栈中。如果遍历完整个数组都没有找到 132 模式，返回 False。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在单调栈的使用中，为什么选择从后往前而不是从前往后遍历数组？
▷🦆
栈中存储的是什么具体的值？是索引还是元素本身？如果是元素，它们如何帮助确定132模式？
▷🦆
题解中提到的'不严格递减栈'的具体含义是什么？这种栈结构如何维护？
▷🦆
变量`right`在算法中起了什么作用？为何它能够代表132模式中的'2'？
▷