1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/132-pattern/description/

2.解题方法

2.1.解题思路

单调栈+逆序遍历

2.2.解题步骤

第一步，构建维护变量。k维护在逆序遍历过程中从栈中弹出的所有元素中的最大值，假设k的索引位置为j，由于弹出的是相对于nums[m]（其中m在i和j之间）更小的元素，所以当nums[i-1]<k时，i-1,m,k就组成了一个「132模式」

第二步，逆向循环遍历数组。更新维护变量，并从栈中不断弹出比当前nums[i]更小的元素

3.解题代码

python代码

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        # 思路：单调栈+逆序遍历
        n = len(nums)
        # 第一步，构建维护变量。k维护在逆序遍历过程中从栈中弹出的所有元素中的最大值，假设k的索引位置为j，由于弹出的是相对于nums[m]（其中m在i和j之间）更小的元素，所以当nums[i-1]<k时，i-1,m,k就组成了一个「132模式」
        k = -inf
        stack = []
        # 第二步，逆向循环遍历数组。更新维护变量，并从栈中不断弹出比当前nums[i]更小的元素
        for i in range(n - 1, -1, -1):
            if nums[i] < k:
                return True
            while stack and stack[-1] < nums[i]:
                k = max(k, stack.pop())
            stack.append(nums[i])
        return False

c++代码

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

4.执行结果