334. Increasing Triplet Subsequence - M 看smart 解法

Q:

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.

A:
----------------------先从后往前找到该位置后面的最大的值---------再从前往后， 看其之前有没有值比他小，而且他又比后面的值小--------------------但是O(n)  space，需要进一步优化------------

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n<3)
            return false;
        vector<int> largerV(n, 0);
        int largestSoFar = nums.back(); // will error if nums is empty
        for(int i = n-1;i >=0; --i)
        {
            largerV[i]=largestSoFar;
            largestSoFar = max(largestSoFar, nums[i]);
        }
        int minBefore = nums[0];
        for(int i = 1; i<n-1;i++)
        {
            if(nums[i] > minBefore and nums[i] < largerV[i])
            {
                return true;
            }
            minBefore = min(minBefore, nums[i]);
        }
        return false;
    }
};

------------------------------------    第二遍  --------------

第一编扫描： 先对每一个位置，确认有个value比他小。 做个标记

第二遍扫描： 确认之前比他小的value都被做了标记

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n < 3){
            return false;
        }
        vector<bool> hasPreI(n,false);
        int minPre = nums[0];
        
        int firstJ = -1;
        for(int i =1;i<n;++i){
            if(nums[i]>minPre){
                hasPreI[i] = true;
                if(firstJ < 0){
                    firstJ = i;
                }
            }
            minPre = min(minPre, nums[i]);
        }
        if(firstJ <0){
            return false;
        }
        // now go find the 2nd round
        int minJ = nums[firstJ];
        for(int k = firstJ ; k<n;++k){
            if( nums[k] > minJ){
                return true;
            }
            if(hasPreI[k]){
                minJ = min(minJ, nums[k]);
            }
        }
        return false;
    }
};

---------------- Greedy --------------------------
这个思路是使用两个指针m1和m2，初始化为整型最大值，我们遍历数组，
如果m1大于等于当前数字，则将当前数字赋给m1；
如果m1小于当前数字且m2大于等于当前数字，那么将当前数字赋给m2，
一旦m2被更新了，说明一定会有一个数小于m2，那么我们就成功的组成了一个长度为2的递增子序列，所以我们一旦遍历到比m2还大的数，我们直接返回ture。
如果我们遇到比m1小的数，还是要更新m1，有可能的话也要更新m2为更小的值，毕竟m2的值越小，能组成长度为3的递增序列的可能性越大，

------------------这里的关键点是， 要 <=  

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int smallest = INT_MAX;// the smallest we see now
        int second_small = INT_MAX;//update when find value k==> m1 < k < m2 (but already bigger than the smallest--m1 )
        for(auto k : nums){
            if(k <= smallest){
                smallest = k;
            }else if(k<=second_small){
                second_small = k;
            }else{
                return true;
            }
        }
        return false;
    }
};