LeetCode 456.132 模式

给你一个整数数组 $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]$。
 

提示：

• $n == nums.length$
• $1 <= n <= 104$
• $-109 <= nums[i] <= 109$

题解

由于要求 $O(n)$，所以只能刷一遍，可以考虑维护左右最大最小值、单调栈等思路。但是简单的使用这些思路并不能维护这个关系

可以认为使用 $O(n)$ 的时间遍历所有的数字，找到:

• 左边最小的数，可以预处理 leftMin 数组维护
• 右边比当前数小的数中最大的，使用单调栈维护

前者比较好处理，后者在维护递减栈的过程中从栈中弹出。

这道题的重点就在于，单调栈弹出的数据也是有意义的，对于递减单调栈，弹出的结果就是所有比当前数小的数，按从小到大弹出。

这是一种新的维护数据的形式，之前并没有考虑过单调栈弹出的数据本身也是有意义的。

代码

type Pair struct {
    Min int
    Max int
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func find132pattern(nums []int) bool {
    n := len(nums)
    
    stack := make([]int, n)
    top := 0

    leftMin := make([]int, n)
    leftMin[0] = math.MaxInt32
    for i := 1; i < n; i++ {
        leftMin[i] = min(leftMin[i-1], nums[i-1])
    }

    for i := n-1; i >= 0; i-- {
        num := nums[i]

        temp := math.MaxInt32
        for top != 0 && stack[top-1] < num {
            top--
            temp = stack[top]
        } 
        if leftMin[i] < temp && leftMin[i] < num && num > temp {
            return true
        }

        stack[top] = num
        top++
    }

    return false
}