456.132模式.md

456. 132 模式

https://leetcode-cn.com/problems/132-pattern/

难度：中等

题目：

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

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

进阶：很容易想到时间复杂度为 O(n^2) 的解决方案，你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？

示例：

示例 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] 。

分析：

这道题重要的就是找到最小的i，然后遍历获取最大J和次大的K，求老大指针，求老大老二，那明显就是单调栈了。 根据这道题，单调递减栈更合适些。

然后，这道题暴力法居然不超时，如果只是为了AC，那这道题难度一下就成了简单了！

解题1:暴力法：

class Solution(object):
    def find132pattern(self, nums):
        N = len(nums)
        numsi = nums[0]
        for j in range(1, N):
            for k in range(N - 1, j, -1):
                if numsi < nums[k] < nums[j]:
                    return True
            numsi = min(numsi, nums[j])
        return False

解题2：单调栈：

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

欢迎关注我的公众号: 清风Python

我的个人博客：https://qingfengpython.cn