问题描述
给定一个整数数组，要求在 O(1) 的空间复杂度内，O(n) 的时间复杂度内判断是否存在三个下标 i、j、k，使得 i < j < k 并且 nums[i] < nums[j] < nums[k]，存在返回 true，不存在返回 false。题目链接：**点我**
样例输入输出
输入：[2,1,5,0,4,6]
输出：true
输入：[5,4,3,2,1]
输出：false
问题解法
从后往前遍历，用变量 curMax 存储三个数中右边最大的数，用 second 存储三个数中中间的数，用 tempMax 存储遍历过程中比 curMax 大的数。在遍历过程中，如果值比 second 小，说明找到了题目要求的三个数，返回 true，如果值比 tempMax 大，则更新 tempMax 的值，如果介于 curMax 和 tempMax 中间，则说明 curMax 和 tempMax 构成了新的三元组中的后两个，如果值介于 second 和 curMax 之间，则更新 second 的值，这样才能尽可能不漏地最快地找到满足要求的三元组。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums.length < 3) {
return false;
}
int curMax = nums[nums.length - 1];
int second = Integer.MIN_VALUE;
int i;
for (i = nums.length - 2; i >= 0; i--) {
if (nums[i] < curMax) {
second = nums[i];
break;
} else {
curMax = nums[i];
}
}
int tempMax = curMax;
for (i--; i >= 0; i--) {
if (nums[i] < second) {
return true;
}
if (nums[i] >= tempMax) {
tempMax = nums[i];
continue;
}
if (nums[i] >= curMax) {
curMax = tempMax;
second = nums[i];
continue;
}
second = nums[i];
}
return false;
}
}
|