Leetcode.334.Increase Triplet Su
2019-12-25 本文已影响0人
Jimmy木
题目
给定一个数组,找到其中是否有三个递增的数。
i < j < k, a[i] < a[j] < a[k]
, 时间复杂度要求O(n),O(1)。
Input: {5,1,5,5,2,5,4}
Output: true
Input: {2,4,-2,-3}
Output: false
Input: {1,6,3,2,5,4}
Output: false
思路
找到两个数是排序的,然后不断更新这个两个有序数,让两个有序数最小。找到比两个有序数大的数即为成功。
bool increasingTriplet(vector<int>& nums) {
if (nums.size() < 3) return false;
int a = nums[0],aa = nums[0],b = INT_MIN;
for (int i = 1; i < nums.size(); i++) {
if (b == INT_MIN) {
if (nums[i] > a) {
b = nums[i];
} else {
a = nums[i];
}
} else if (nums[i] > a && nums[i] < b) {
b = nums[i];
} else if (nums[i] > aa && nums[i] < b) {
a = aa;
b = nums[i];
} else if (nums[i] < a) {
aa = nums[i];
} else if (b > a && nums[i] > b) {
return true;
}
}
return false;
}
总结
需要仔细分析各种情况,思路要清晰,要把if分析的滴水不漏。