Leetcode.334.Increase Triplet Su

题目

给定一个数组，找到其中是否有三个递增的数。
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分析的滴水不漏。