看了 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 。
代码:
publicbooleanfind132pattern(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]) {