问题描述:

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.

题意：

给定一无序数组，判断其中是否存在长度为3的递增子序列。

解题思路:

此问题可转化为先找长度为2的递增序列（记为first, second）然后再判断后面是否有比second更大的数。此时我们只需维护first, second，但可能出现如3,4,1这种情况，这时我们就需要另一个数temp表示位于递增序列后面但比first更小的数。之后对于数组中的每一个数nums[i]，只需根据其在temp，first，second三者之间的位置来判断结果并维护这三个数，其中包括[负无穷, temp]，(temp, first]，(first, second]，(second, 正无穷)四个区间

示例代码:

class Solution {

public:

    bool increasingTriplet(vector<int>& nums) {

        int len = nums.size();

        if(len < 3){

            return false;

        }

        int first = nums[0], second = INT_MAX, temp = nums[0];

        for(int i = 1; i < len; i++){

            if(nums[i] > second){

                return true;

            }

            if(nums[i] > first){

                second = nums[i];

            }

            else if(nums[i] <= temp){

                temp = nums[i];

            }

            else{

                first = temp;

                second = nums[i];

            }

        }

        return false;

    }

};