题目描述

给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成,并同时满足:i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ,返回 true ;否则,返回 false 。

示例

输入:nums = [1,2,3,4]
输出:false
解释:序列中不存在 132 模式的子序列。
输入:nums = [3,1,4,2]
输出:true
解释:序列中有 1132 模式的子序列: [1, 4, 2] 。

题目解析

  1. 维护一个栈,存放最大的元素的下标
  2. 倒序遍历数组,如果当前元素比栈顶元素大就将栈顶元素弹栈,并记录k的下标最大值
  3. 将当前元素压栈
  4. 如过当前元素的下标小于k的下标,则存在132模式
    1. 因为倒序遍历的原因,栈中存放的是最大值的下标,因此k是比最大值小的元素,如果出现比k小的元素说明存在132模式