LeetCode-456 132 模式

Table of Contents

LeetCode-456 132 模式 #

Solution 1 #

对于三元组 $(i,j,k)$ , 我们考虑枚举 $i$ , 怎么维护 $(j, k)$ 使得 $nums[j] > nums[k]$ 呢? 答案是单调栈. 将 $i$ 右侧第一个数据入栈, 之后遇到比栈顶小的数据就入栈, 否则出栈, 用 $maxk$ 表示出栈元素的最大值, 假如有 $maxk > nums[i]$ , 则必有合法的三元组 $(i,j,k)$ , 这是因为 $maxk$ 出栈是因为有一个更大元素要入栈使得单调减序列不再成立, 这个序列的下标就是我们要找的 $j$ , 而 $maxN$ 的下标就是我们要找的 $k$ . 代码如下:

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        s = [nums[-1]]
        max_k = -inf
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] < max_k:
                return True
            while s and s[-1] < nums[i]:
                max_k = max(max_k, s.pop())
            s.append(nums[i])
        return False

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> st;
        int n = nums.size(), k = INT_MIN;
        for(int i = n - 1; i >= 0; i--){
            if(nums[i] < k) return true;
            while(!st.empty() and st.top() < nums[i]) { 
                k = max(k,st.top()); st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
};