0456. 132 模式【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 单调栈

1. 📝 题目描述

• leetcode

给你一个整数数组 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

2. 🎯 s.1 - 单调栈

c

bool find132pattern(int* nums, int numsSize) {
    int* stack = (int*)malloc(sizeof(int) * numsSize);
    int top = 0;
    int third = INT_MIN;
    for (int i = numsSize - 1; i >= 0; i--) {
        if (nums[i] < third) { free(stack); return true; }
        while (top > 0 && stack[top - 1] < nums[i])
            third = stack[--top];
        stack[top++] = nums[i];
    }
    free(stack);
    return false;
}

js

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function (nums) {
  const n = nums.length
  const stack = []
  let third = -Infinity // nums_k ("2" in 132)
  for (let i = n - 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
}

py

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        third = float('-inf')
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] < third:
                return True
            while stack and stack[-1] < nums[i]:
                third = stack.pop()
            stack.append(nums[i])
        return False

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 从右往左遍历，维护单调递减栈
• third 记录被弹出的最大值（即 132 中的 "2"）
• 若当前元素 < third，则找到了 132 模式