LeetCode 456.132 模式

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

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

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

示例 1

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

示例 2

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

示例 3

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

提示：

• n==nums.lengthn == nums.length
• 1<=n<=1041 <= n <= 104
• −109<=nums[i]<=109-109 <= nums[i] <= 109

题解

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

可以认为使用 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
}