LeetCode/递增的三元子序列

给你一个整数数组nums ，判断这个数组中是否存在长度为 3 的递增子序列

1. 贪心法

贪心更新两个最左端端点

class Solution {
public:
  bool increasingTriplet(vector<int>& nums) {
    int len = nums.size();
    if (len < 3) return false;
    int small = INT_MAX, mid = INT_MAX;//初始皆赋最大值
    for (auto num : nums) {
      if (num <= small) small = num;//贪心选择左端点
      else if (num <= mid) mid = num;//贪心更新中间端点
      else if (num > mid) return true;
    }
    return false;    
  }
};

2. 动态规划

求最长递增子序列

class Solution {
public:
  bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        vector<int> dp(n); //dp[i]记录i长度序列的最后元素值
        int res = 0;
        for(int k=0;k<n;k++){
           int i =0;int j =res;//res 为当前最长长度
           while(i<j){
               int m = (i+j)/2;
               if(dp[m]<nums[k]) i=m+1;//移动左边界，最终移到恰满足条件的下一位置
               else j=m; //移动右边界
           }
        dp[i] = nums[k];//把该元素作为最小元素替换下一序列长度
        if(j==res) res++;//如果该位置拓宽了最大长度，最大长度更新
        if(res>=3) return true;
    }
    return false; 
  }
};

3. 双单调栈

记录每个位置左侧（右侧）是否有更小值（更大值）

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if(nums.size()<3) return 0;
        vector<bool> left(nums.size());
        vector<bool> right(nums.size());
        stack<int> s1,s2;
        for(int i=0, j=nums.size()-1;i<nums.size();i++,j--){
            while(!s1.empty()&&nums[i]>nums[s1.top()]){
                right[s1.top()] = true;
                s1.pop(); 
            }
            while(!s2.empty()&&nums[j]<nums[s2.top()]){
                left[s2.top()] = true;
                s2.pop(); 
            }
            s1.push(i);
            s2.push(j);
        }
        for(int i=0;i<nums.size();i++)
            if(left[i]&&right[i]) return true;
        return false;
  }
};