数组[3,5,0,3,4]检测异常，求修正132 pattern检测代码逻辑

一、为什么数组[3,5,0,3,4]符合132 Pattern？ #

根据132 Pattern的定义，只需找到任意三个索引i<j<k满足nums[i] < nums[k] < nums[j]即可。在数组[3,5,0,3,4]中，存在这样的有效子序列：

• i=0（值为3），j=1（值为5），k=4（值为4）
  满足3 < 4 < 5，完全符合132 Pattern的条件，因此该数组应返回true。

二、原代码的逻辑错误分析 #

你的代码存在两个核心问题：

1. 仅检查连续三元组：代码每次只检查l, mid, r这三个连续索引的元素（比如0,1,2；1,2,3；2,3,4），但132 Pattern的i、j、k不需要是连续索引，像前面提到的0,1,4这种非连续组合会被直接遗漏。
2. 错误限定j的位置：代码把j固定为mid=(l+r)/2（i和k的中间位置），但实际上j可以是i和k之间的任意索引，只要满足i<j<k即可，这进一步缩小了检查范围，导致大量符合条件的情况无法被检测到。

三、修正后的代码实现 #

以下提供两种常见的正确实现方式：

方法1：枚举j，预处理左侧最小值+右侧遍历（时间复杂度O(n²)） #

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;
        
        // 预处理每个位置j左侧的最小值（即可能的i对应的nums[i]）
        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        for (int j = 1; j < n; j++) {
            leftMin[j] = Math.min(leftMin[j-1], nums[j]);
        }
        
        // 枚举每个j，检查右侧是否存在k>j，满足leftMin[j] < nums[k] < nums[j]
        for (int j = 1; j < n-1; j++) {
            for (int k = j+1; k < n; k++) {
                if (leftMin[j] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

方法2：单调栈优化（时间复杂度O(n)） #

这是更高效的解法，从右往左遍历，用栈维护可能的nums[k]候选，同时记录当前最大的nums[k]值：

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;
        
        // 栈中存储可能的nums[k]候选，保持单调递减
        Deque<Integer> stack = new ArrayDeque<>();
        // 记录当前找到的最大nums[k]（满足nums[k]<nums[j]的最大k值）
        int maxK = Integer.MIN_VALUE;
        
        // 从右往左遍历每个元素作为nums[j]
        for (int j = n-1; j >= 0; j--) {
            // 当前nums[j] > maxK，说明存在k>j使得nums[k]=maxK < nums[j]，只需左侧有i<j满足nums[i]<maxK即可
            if (nums[j] > maxK) {
                // 弹出栈中所有小于等于nums[j]的元素，更新maxK为栈中弹出的最大元素
                while (!stack.isEmpty() && stack.peek() < nums[j]) {
                    maxK = stack.pop();
                }
            }
            // 当前nums[j] < maxK，说明存在i<j（左侧任意小于maxK的元素），满足nums[i]<maxK<nums[j]
            if (nums[j] < maxK) {
                return true;
            }
            // 将当前元素压入栈，作为后续可能的nums[k]候选
            stack.push(nums[j]);
        }
        return false;
    }
}

内容的提问来源于stack exchange，提问作者Alhaseena