【暴力, 单调栈】132 模式

题目

456. 132 模式

---

给你一个整数数组 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

解题

方法一：遍历j 暴力

思路

$i < \boxed{j} < k$ $nums[i] < nums[k] < \boxed{nums[j]}$

从左到右枚举下标 j：

• 由于 i 是 i, j, k 中的最小值，因此我们在枚举 j 的同时，维护数组 nums 中左侧元素 $nums[0..j-1]$ 的最小值，即为 i 对应的元素 nums[i]。
  需要注意的是，只有 nums[i] < nums[j] 时，nums[i] 才是一个合法的 i 对应的值。
• 由于 k 是 i, j, k 中的次小值，可以使用一个有序集合（例如平衡树）维护数组 nums 中右侧元素 $nums[j+1..n-1]$ 中的所有值。
  当我们确定了 nums[i] 和 nums[j] 之后，只需要在有序集合中查询严格比 nums[i] 大的那个最小的元素，即为 nums[k]。
  需要注意的是，只有 nums[k] < nums[j] 时，nums[k] 才是一个合法的 k 对应的值。

代码

class Solution {
    public boolean find132pattern(int[] nums) {
        int len = nums.length;
        if (len < 3) return false;
        int leftMin = nums[0]; // j左边的最小值
        TreeMap<Integer, Integer> rightPart = new TreeMap<>(); // j右边的所有值对应其出现次数
        for (int k = 2; k < len; k++) {
            rightPart.put(nums[k], rightPart.getOrDefault(nums[k], 0) + 1);
        }
        for (int j = 1; j < len - 1; j++) {
            int mid = nums[j]; // 当前遍历到的j在数组中的对应值
            if (leftMin < mid) {
                // 找到严格比nums[i]大的那个最小的元素
                Integer right = rightPart.ceilingKey(leftMin + 1);
                // 找得到且nums[k] < nums[j]则找到了合法的值
                if (right != null && right < mid) return true;
            }
            // 维护j左边的最小值
            leftMin = Math.min(leftMin, mid);
            // 因为j会右移一位, 所以平衡树中要删除一个在原数组中的nums[j + 1]
            int nextMid = nums[j + 1], count = rightPart.get(nextMid) - 1;
            if (count == 0) rightPart.remove(nextMid);
            else rightPart.put(nextMid, count);
        }
        return false;
    }
}

方法二：单调栈

思路

维护一个单调递减栈，单调栈中存可能成为 nums[j] 的值，在维护一个 kNum 表示 k 可能对应的值，初始化为 $-\infin$，从右向左枚举 i：

• 如果 nums[i] < kNum，找到了合法的 i, j, k 直接返回 true。
• 如果栈不为空且 nums[i] 大于栈顶元素时，不断地出栈并赋值给 kNum。
• 否则 nums[i] 进栈。

由上面的步骤不难发现：kNum 如果不是初始值的 $-\infin$ ，则说明 j, k 已经被找到：

• 这是因为存在的 kNum 是从单调递减栈中出栈得到的（$kNum < 单调递减栈栈顶元素$）。
• 而单调递减栈的栈顶表示可能的 nums[j] 值，所以一定有 kNum < nums[j] 。
• 又因为遍历时从右向左进行的，那么先出栈的元素的索引一定大于栈中元素的索引，所以一定有 kNum 的索引 k $<$ 栈顶元素的索引 j，也就是 k < j。

所以说 j, k 已经被找到。剩下的工作就是验证 i < j 与 nums[i] < kNum：

• 因为 i 是从右向左反向遍历来的，所以索引 i 一定是 $\{i, kNum对应的索引k, 栈顶元素对应的索引j\}$ 这三个中最小的，i < j < k 得证。
• 此时只需要保证 nums[i] < kNum 就说明合法的一组 i, j, k 已经被找到，也就是判断返回条件的由来。

代码

class Solution {
    public boolean find132pattern(int[] nums) {
        int len = nums.length;
        if (len < 3) return false;
        Deque<Integer> stack = new LinkedList<>();
        int kNum = Integer.MIN_VALUE;
        // 反向遍历保证了 i < j < k
        for (int i = len - 1; i >= 0; i--) {
            int iNum = nums[i];
            // 缺少的条件: nums[i] < nums[k] 一旦成立便直接返回 true
            if (iNum < kNum) return true;
            while (!stack.isEmpty() && iNum > stack.peek()) {
                // 保证了kNum < 栈顶元素
                kNum = stack.pop();
            }
            stack.push(iNum);
        }
        return false;
    }
}