友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
456. 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.length -
1 <= n <= 2 * 105 -
-109 <= nums[i] <= 109
思路分析
完全没有想到竟然可以使用单调栈来解决！
从右向左遍历，使用一个单调递减栈，来维护 32 的关系：弹出的就是 2，栈中的就是 3，当前元素小于 k 时，就找到了 132 模式。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-08-24 19:46:45
*/
public boolean find132pattern(int[] nums) {
int n = nums.length;
Deque<Integer> stack = new ArrayDeque<>();
int k = Integer.MIN_VALUE;
for (int i = n - 1; i >= 0; i--) {
// k 初始化时是 Integer.MIN_VALUE，
// 当出现小于 k 的元素时，说明 k 被更新过了，
// 也说明栈中有元素且比 k 大
if (nums[i] < k) {
return true;
}
// 单调递减栈，遇到大的元素，就把小的都弹出来
while (!stack.isEmpty() && stack.peekLast() < nums[i]) {
// 在弹出来的小的元素里面，找最大的元素
k = Math.max(k, stack.pollLast());
}
stack.addLast(nums[i]);
}
return false;
}