[数据结构与算法]LeetCode 456. 132 Pattern - 单调栈（Monotonic Stack）系列题6

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.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

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

题目给定一个整型数组，问是否存在三个数的子序列满足132模式，所谓132模式就是三个数保持数组中的顺序，第三个数大于第一个数但小于第二个数。

这题是一道变形的单调栈类型题，要是不放在单调栈系列里刷是很难想到可以用单调栈的。先来分析一下题目，首先数组长度必须大于等于3，然后再来分析一下数组中的一个数都在什么情况下满足或不满足132模式。对于数组中的一个数，如果它是作为序列中的第三个数并且小于等于它前面所有数的最小值，那么它跟前面所有数肯定无法形成132模式，这种情况下这个数对于它前面所有数来说就是没用的了，但它还是有可能作为它后面数的第1个或第2个数，反过来要是它后面所有数都已经判断过了那么这个数就可以彻底被排除了。

因此我们可以从后到前遍历数组挨个判断每个数，用一个堆栈来存放潜在的数，当遍历到当前数nums[i]时会有如下3种情况

1）堆栈里的数只要小于等于从i到0所有数的最小值的数就可以被弹出栈排除掉，

2）只要栈顶的数大于从i到0所有数的最小值并且小于当前数nums[i]，那么至少存在一个132模式的序列，可以直接返回True

3）同时不满足情况1)和2)的数就是不确定的潜在的数，可以暂时压入堆栈。

遍历完整个数都没出现情况2），说明整个数组不存在132模式，返回False。

另外为了快速得到当前数到数组头的最小值，可以事先计算好存放在一个辅助数组里。

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        
        st = []
        minNums = [0] * n #the minmum num from the begining to the current 
        minNums[0] = nums[0]
        for i in range(1, n):
            minNums[i] = min(minNums[i - 1], nums[i])
            
        for i in range(n - 1, -1, -1):
            while st and st[-1] <= minNums[i]:
                st.pop()
            if st and st[-1] < nums[i]:
                return True
            st.append(nums[i])
        
        return False