Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

思路

首先寻找一个前后递增的关系，即找到序列中，后一个数比前一个数大的情况。如果没有则返回False。这是在第一个while循环里面进行的。

接下来我们寻找第三个数，如果找到的第三个数比前两个数都要大，返回True。

我们把前面找到的两个数分别维护起来，分别为low和mid。如果找到的数如果比mid小，却low大，将mid的值置换为该数；

如果找到的数比low小，可以暂存起来，放进low_tmp中，看此数之后还有没有比它大的数。

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
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if (nums.size() <= 2){
            return false;
        }
        else{
            int i = 1;
            while(nums[i] - nums[i-1] <= 0){
                i++;
                if (i == nums.size()){
                    return false;
                    break;
                }
            }
            int low = nums[i-1];
            int mid = nums[i];
            int low_tmp = nums[i-1];
            while(i < nums.size() - 1){
                i++;
                if(nums[i] <= low_tmp){
                    low_tmp = nums[i];
                }
                if(nums[i] <= mid && nums[i] > low_tmp){
                    mid = nums[i];
                    low = low_tmp;
                }
                if(nums[i] > mid){
                    return true;
                }
            }
            return false;
            
        }
    }
};