Poison

334. Increasing Triplet Subsequence

Traverse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean increasingTriplet(int[] nums) {
int[] leftMin = new int[nums.length]; // 左侧至当前下标(含)的最小值
leftMin[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
leftMin[i] = Math.min(nums[i], leftMin[i - 1]);
}

int[] rightMax = new int[nums.length]; // 右侧至当前下标(含)的最大值
rightMax[rightMax.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {
rightMax[i] = Math.max(nums[i], rightMax[i + 1]);
}

for (int i = 1; i < nums.length - 1; i++) {
// 注意此处比较的为 leftMin[i - 1] 与 rightMax[i + 1]
if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
return true;
}
}

return false;
}
}
Greedy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums.length < 3) {
return false;
}

int first = nums[0], second = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
if (num > second) {
return true;
} else if (num > first) {
second = num;
} else {
first = num;
}
}

return false;
}
}
Reference

334. Increasing Triplet Subsequence