Leetcode--456-132模式

Leetcode–456-132 模式

题目描述

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

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

注意：

进阶：很容易想到时间复杂度为 O(n^2) 的解决方案，你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？

示例 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 <= 10^4
• -10^9 <= nums[i] <= 10^9

算法思路

思路

• 由于本题中的n 最大值为10^4，因此对一个满足132的三元组下标（i,j,k），枚举其中两个下标的时间复杂度是O(n^2),很容易超出时间的限制
• 因此我们可以考虑枚举其中的 1个下标，并使用合适的数据结构维护另外的 2 个下标的可能值。

算法：枚举3

• 枚举 3 是容易想到并且也是最容易实现的。由于 3 是模式中的最大值，并且其出现在 1 和 2 的中间，因此我们只需要从左到右枚举 3 的下标 j，那么：

class Solution {
    public boolean find132pattern(int[] nums) {
        // 1. 特判 : 少于三个元素不能构成132
        int n = nums.length;
        if(n < 3){
            return false;
        }

        // 2. 定义左侧最小值
        int leftMin = nums[0];

        // 3. 将右侧所有元素放进到有序集合中
        TreeMap<Integer,Integer> rightAll = new TreeMap<Integer,Integer>();
        for(int k = 2;k < n;++k){
            rightAll.put(nums[k],rightAll.getOrDefault(nums[k],0) + 1);
        }

        // 3. 枚举3
        for(int j = 1;j < n - 1;++j){
            // 3.1 满足132中的nums[i] < nums[j]的条件
            if(leftMin < nums[j]){              
                Integer next = rightAll.ceilingKey(leftMin + 1);        // ceilingKey：方法调用返回的最小的大于或等于的键，如果不存在这样的键在则返回null。（这里的作用是返回TreeMap 中的大于leftMin的最小值）
                if(next != null && next < nums[j]){                     // 如果这个最小值存在且小于nums[j]:说明满足132的整体条件
                    return true;
                }
            }
            // 3.2 不满足132中：nums[i] < nums[j] 条件
            leftMin = Math.min(leftMin, nums[j]);                       // 更新leftMin（nums[i]）的值
            rightAll.put(nums[j + 1], rightAll.get(nums[j + 1]) - 1);   // 将有序集合中的nums[j + 1]对应的键值-1 相当于将“窗口”右移一位
            if(rightAll.get(nums[j + 1]) == 0){                         // 若有序集合中的nums[j + 1]对应的键值==0 删除这个键值对
                rightAll.remove(nums[j + 1]);
            }
        }
        // 枚举结束未找到返回false
        return false;
    }
}

打赏