题目

题目来源：力扣（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] 。

思路分析

  • 我们要找到这样的三个下标：I<J<K，满足nums[I]<nums[K]<nums[J]。
  • 假设当前元素 nums[J],要找在 J 之后比 nums[J] 小的数 nums[K],和在 J 之前比 nums[K] 小的数 nums[I],我们可以建立栈从后往前存储数组的元素（或下标），在栈中找nums[K]，再继续向前扫描找 nums[I]。栈中要能够保存比nums[J]下标更大并且值更小的元素，联想到去维护一个单调递减栈，栈中存储的是下标。
  • 可以这样去模拟过程：

从后往前扫描的过程中，一旦当前元素 nums[I] 比栈顶大，这个 nums[I] 或许就是我们要找的 nums[J]，弹出栈中所有的比它小的元素，这些元素就是符合条件的 nums[K],最后一个弹出的就是符合条件的最大 nums[K],如果这个 num[K] 比继续往前扫描到的 nums[I] 要大，则符合条件。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {boolean}
  4.  */
  5. var find132pattern = function (nums) {
  6.   //单调栈维护所有可以作为 132 模式中 2 的候选元素，栈中元素值比 nums[j] 大，并且下标比最大值nums[j] 的下标大
  7.   let stack = [];
  8.   // 变量 med 维护 132 中所有可以真正作为 2 的元素的最大值，（即 132 模式中的次大值），初始化为 负无穷大
  9.   let med = -Infinity;
  11.   // 而按题目要求，peek的下标需要比cur大，所以我们从数组的右边往左遍历，使得先进栈的元素对应下标更大。
  13.   // 从右往左遍历枚举的是 132 中的 1，即 132 模式中的最小值
  14.   // 在从右往左遍历的过程中，如果当前遍历的元素 nums[i] 比栈顶元素大，那么这个 nums[i] 有可能是我们要找的 最大值，
  15.   // 弹出栈中所有比 nums[i] 小的元素，这些元素都是符合条件 次小值 med，最后一个弹出的就是符合条件的最大的 次小值 med
  16.   for (let i = nums.length - 1; i >= 0; i--) {
  17.     // 如果当前遍历的元素 nums[i] 比次大值 小，说明当前遍历的元素就是 132 模式中的 1，即最小值
  18.     if (nums[i] < med) return true
  19.     // 当前元素 nums[i] 比栈顶大，这个 nums[i] 或许就是我们要找的最大值 nums[J]
  20.     while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
  21.       // 维护所有被移除的元素的最大值（即最大的 次小值）
  22.       med = stack.pop()
  23.     }
  24.     stack.push(nums[i])
  25.   }
  26.   // 遍历完所有的元素后，如果仍未找到满足 132 模式的三元组，那就说明其不存在，返回 false
  27.   return false
  28. };