Medium

题目描述

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

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

示例 1：

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

示例 2：

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2]。

示例 3：

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0]。

提示：

  • n == nums.length
  • 1 <= n <= 2 * 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

解题思路

这道题要找到满足 nums[i] < nums[k] < nums[j] 且 i < j < k 的三元组。

方法一：暴力解法 O(n³)

枚举所有可能的三元组，但时间复杂度过高。

方法二：优化暴力 O(n²)

固定中间元素 j，向左找最小值作为 nums[i]，向右找满足条件的 nums[k]。

方法三：单调栈（推荐）

这是最优解法，核心思想：

  1. 从右向左遍历，维护一个单调递减栈
  2. 栈中存储潜在的 nums[k] 值（即 132 模式中的"2"）
  3. 维护一个变量 third，表示当前找到的最大的 nums[k] 值
  4. 对于当前元素，如果它小于 third，说明找到了 132 模式

具体过程：

  • 遍历到元素时，先弹出栈中所有小于等于当前元素的值，这些值可以作为潜在的 nums[k]
  • 用弹出的最大值更新 third（这样 third 就是目前能找到的最大的中间值）
  • 如果当前元素小于 third，说明找到了 132 模式
  • 将当前元素入栈

时间复杂度 O(n)，每个元素最多入栈出栈一次。

代码实现

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

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        
        stack = []
        third = float('-inf')
        
        for i in range(n - 1, -1, -1):
            if nums[i] < third:
                return True
            
            while stack and stack[-1] < nums[i]:
                third = stack.pop()
            
            stack.append(nums[i])
        
        return False

public class Solution {
    public bool Find132pattern(int[] nums) {
        int n = nums.Length;
        if (n < 3) return false;
        
        Stack<int> stack = new Stack<int>();
        int third = int.MinValue;
        
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < third) {
                return true;
            }
            
            while (stack.Count > 0 && stack.Peek() < nums[i]) {
                third = stack.Pop();
            }
            
            stack.Push(nums[i]);
        }
        
        return false;
    }
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function(nums) {
    const n = nums.length;
    if (n < 3) return false;
    
    const stack = [];
    let third = -Infinity;
    
    for (let i = n - 1; i >= 0; i--) {
        if (nums[i] < third) {
            return true;
        }
        
        while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
            third = stack.pop();
        }
        
        stack.push(nums[i]);
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度单调栈解法
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：每个元素最多入栈和出栈各一次，总体为 O(n)
  • 空间复杂度：栈最多存储 n 个元素，为 O(n)