leetcode：456. 132 mode [monotone stack]

analysis

We found at a glance nums[k] In the middle , Decisive analysis k
So because k Maximum index , We looked in reverse order k
Then maintain a decreasing stack in reverse order , In this way, you can find every k The next one is bigger than him nums[j]
This will satisfy kj The relationship between , Then every time a bigger one comes j, We can all update kj, bring k As big as possible
such i It is more likely to be found （ greedy ）,for At the beginning of the cycle, judge if ik If the relationship is satisfied

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

summary

Monotonic stack + greedy + thinking