Topic

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

Example_1

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

Example_2

输入：nums = [3,1,4,2] 输出：true 解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

Example_3

输入：nums = [-1,3,2,0] 输出：true 解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

Tips

n == nums.length 1 <= n <= 2 * 105 -109 <= nums[i] <= 109

Solution

利用单调递减栈解决本题

通过枚举i找到最小的i 然后遍历获取最大J和次大的K

Code

class Solution:
    def find132pattern(self, nums):
        min_list = [nums[0]]
        for i in range(1, len(nums)):
            min_list.append(min(min_list[-1], nums[i]))
        stack = []
        for j in range(len(nums) - 1, -1, -1):
            while stack and stack[-1] < nums[j]:
                k = stack.pop()
                if k > min_list[j]:
                    return True
            stack.append(nums[j])
        return False

Res