侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【暴力, 单调栈】132 模式

GabrielxD
2022-05-29 / 0 评论 / 0 点赞 / 148 阅读 / 1,334 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

456. 132 模式


给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]nums[j]nums[k] 组成,并同时满足:i < j < knums[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<j<ki < \boxed{j} < k nums[i]<nums[k]<nums[j]nums[i] < nums[k] < \boxed{nums[j]}

从左到右枚举下标 j

  • 由于 i 是 i, j, k 中的最小值,因此我们在枚举 j 的同时,维护数组 nums 中左侧元素 nums[0..j1]nums[0..j-1] 的最小值,即为 i 对应的元素 nums[i]
    需要注意的是,只有 nums[i] < nums[j] 时,nums[i] 才是一个合法的 i 对应的值。
  • 由于 k 是 i, j, k 中的次小值,可以使用一个有序集合(例如平衡树)维护数组 nums 中右侧元素 nums[j+1..n1]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<单调递减栈栈顶元素kNum < 单调递减栈栈顶元素)。
  • 而单调递减栈的栈顶表示可能的 nums[j] 值,所以一定有 kNum < nums[j]
  • 又因为遍历时从右向左进行的,那么先出栈的元素的索引一定大于栈中元素的索引,所以一定有 kNum 的索引 k << 栈顶元素的索引 j,也就是 k < j

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

  • 因为 i 是从右向左反向遍历来的,所以索引 i 一定是 {i,kNum对应的索引k,栈顶元素对应的索引j}\{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;
    }
}
0
博主关闭了所有页面的评论