LeetCode 456 - 132 Pattern

作者 QIFAN 日期 2017-01-02
LeetCode 456 - 132 Pattern

原题链接:456. 132 Pattern


题干

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

  1. $i < j < k$
  2. $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