456.132模式

链接：456.132模式
难度：Medium
标签：栈、数组、二分查找、有序集合、单调栈
简介：给定一个整数序列：a1, a2, ..., an，一个 132 模式的子序列  ai, aj, ak  被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有  n 个数字的序列时，验证这个序列中是否含有 132 模式的子序列。

题解 1 - typescript

• 编辑时间：2021-03-24
• 执行用时：112ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：单调栈。

function find132pattern(nums: number[]): boolean {
  const len = nums.length;
  if (len < 3) return false;
  const stack: number[] = [];
  let num2: number = -Infinity;
  for (let i = len - 1; i >= 0; i--) {
    const num = nums[i];
    if (num < num2) return true;
    while (stack.length > 0 && stack[stack.length - 1] < num) num2 = stack.pop()!;
    stack.push(num);
  }
  return false;
}

题解 2 - typescript

• 编辑时间：2021-07-20
• 执行用时：92ms
• 内存消耗：53.2MB
• 编程语言：typescript
• 解法介绍：找当前值，左侧最小值和右侧不大于当前值的最大值。

function find132pattern(nums: number[]): boolean {
  const n = nums.length;
  const l: number[] = [Infinity];
  for (let i = 1; i < n; i++) l[i] = Math.min(l[i - 1], nums[i - 1]);
  const stack: number[] = [];
  for (let i = n - 1; i >= 0; i--) {
    const mid = nums[i];
    let r: number | null = null;
    while (stack.length && stack[stack.length - 1] < mid) r = stack.pop()!;
    if (r && mid > r && mid > l[i] && r > l[i]) return true;
    stack.push(mid);
  }
  return false;
}