Manjusaka

09-30 leetcode 0456

链接 456. 132 Pattern

题目

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

题解

这题因为只需要找到 132 是否存在，核心在于这样，

1. 在 j 的左侧找到一个最小的数，这个数要小于 j
2. 在 j 的右侧找到一个最大的数，这个数要小于 j
3. 1 和 2 中的数要满足 1 < 2

我们1很好求，只需要维护一个最小值就可以了，但是 2 怎么求呢？

单调栈，严格来说是单调递减栈，出栈的最后一个元素就可以认为是小于 j 的最大值。右侧的话就从右往前遍历就可以了。

MAGIC = 2 * (10**9) + 1


class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        min_index = [MAGIC] * len(nums)
        for i in range(1, len(nums)):
            min_index[i] = min(min_index[i - 1], nums[i - 1])
        min_index[0] = nums[0]
        stack = []
        for i in range(len(nums) - 1, -1, -1):
            temp = -MAGIC
            while stack and nums[i] > stack[-1]:
                temp = stack.pop()
            if min_index[i] < temp:
                return True
            stack.append(nums[i])
        return False

这里遍历了两次，其实可以只遍历一次，同时可以减少一个数组的使用

我们用一个数记录最后出栈的一个元素 k，由于前面说过的单调栈的特性，在我们从右向左的过程中，如果当前元素 i < k ，那么一定存在一个元素 j 满足，i < j < k, 132 模式成立

MAGIC = 2 * (10**9) + 1

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