LeetCode 456 - 132 Pattern

原题链接：456. 132 Pattern

题干

给定一串数字数组 $a_1, a_2, a_3, …, a_n$，如果有三个数 $a_i, a_j, a_k$ 满足下列条件：

$i < j < k$
$a_i < a_k < a_j$

那这三个数就是一个 132 模式。而这道题要求返回数组中是否存在 132 模式。

note：n < 15000

思路

第一个想法就是简单粗暴的 $O(n^3)$，一个一个的找，这当然是会超时间的。我们需要 improve 一下。

观察到 $a_k$ 是落在 $a_i$ 与 $a_j$ 之间，我们想尽可能快的找到 $a_k$，所以会希望 $(a_i, a_j)$ 的这个范围尽可能大。所以在 j 不变的情况下，i 应该是 $(a_0, a_j)$ 间的最小值。

代码：

public boolean find132Pattern(int[] nums) {
    int min = Integer.MAX_VALUE;
    for (int j = 0; j < nums.length; j++) {
        min = Math.min(nums[j], min);
        if (min == nums[j]) {
            continue;
        }
        for (int k = j + 1; k < nums.length; k++) {
            if (min < nums[k] && nums[j] > nums[k]) {
                return true;
            }
        }
        return false;
    }
}

如果面试官问，还能更好吗，我可能就没法子了。

看了 discussion 里有一句话说的很对：to further reduce the time complexity, we need to record the “useful” information about elements in the right part of the input array nums 。现在时间主要花在找 k 上，每次都要将整个右边部分每个比较，其实很浪费时间，其实如果我们知道右边部分的最小值和最大值，只要它们任意一个落在$(a_i, a_j)$ 内，那就一定存在 132 pattern 。

代码：

public boolean find132pattern(int[] nums) {
    int[] minArr = Arrays.copyOf(nums, nums.length);
    int[] maxArr = Arrays.copyOf(nums, nums.length);
    for (int k = nums.length - 2; k >= 0; k--) {
        minArr[i] = Math.min(nums[k + 1], minArr[k + 1]);
        maxArr[k] = Math.max(nums[k + 1], maxArr[k + 1]);
    }
    
    int min = nums[0];
    for (int j = 1; j < nums.length; j++) {
        min = Math.min(nums[j - 1], min);
        if (min == nums[j]) {
            continue;
        }
        if (nums[j] == minArr[j]) {
            continue;
        }
        if (nums[j] > min && maxArr[j] > minArr[j] && maxArr[j] < nums[j]) {
            return true;
        }
    }
        
    return false;
}

这题还有一个用 stack 的方法：Java O(n) solution using stack in detail explanation

题干
思路

LeetCode 456 - 132 Pattern

题干

思路

FEATURED TAGS

FRIENDS