456. 132 模式

Difficulty
Medium
Tags
单调栈
URL
https://leetcode-cn.com/problems/132-pattern/
Star
给你一个整数数组 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
通过次数63,164提交次数174,289

法 1 单调栈

思路
单调栈有个好处，例如从右往左单调递减的曲线↙，他可以突然发现一个突然升高，构成一个V字结构，之后退栈行成全新的右到左的曲线↙，如果后面是新的元素可以继续构成从右到左的下降曲线↙，如果这个时候回过头想想刚刚的 V 字结构，这个时候算上新加的元素，刚好构成一个 N 字结构，这个时候只要判断这个N的左边是否是132就行了，也就是判断新点的原V结构的最低点的大小比
通过 [3,5,0,3,4] 来理解
题解
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        prev_top = -float("inf")
        for i in range(len(nums)-1, -1, -1):
            if nums[i] < prev_top:
                return True
            # 来了 一个新的 top
            while stack and nums[i] > nums[stack[-1]]:
                prev_top = nums[stack.pop()]
            
            stack.append(i)

        return False