leetcode：456. 132 模式【单调栈】

分析

我们一眼发现nums[k]在中间，果断分析k
因此由于k索引最大，我们倒序找k
然后倒序来维护一个递减栈，这样就可以找到离每个k最近的下一个比他大的nums[j]
这样就可以满足kj的关系，然后每次来了更大的j，我们都可以更新kj，使得k尽量大
这样i可找到的可能性就更大（贪心），for循环一开始判断如果ik关系满足即可

ac code

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        # nums[k] is in the middle
        # we consider k

        n = len(nums)
        v_k = -inf # nums[k]
        st = [] 

        # reverse and next bigger than myself
        for i in range(n - 1, -1, -1):
            if nums[i] < v_k:
                return True
            # make sure there is a j s.t. nums[j] > nums[k] while j < k
            while st and st[-1] < nums[i]: # nums[k] < nums[j], make nums[k] as big as possible(greedy), so that it can find i easier
                v_k = st.pop()
            
            st.append(nums[i]) # keep a decreasing stack
        
        return False

总结

单调栈 + 贪心 + 思维