LeetCode 334. 递增的三元子序列（C++）

····思路：
1.对于任何位置，只需要满足i < j < k ，使得 nums[i] < nums[j] < nums[k]；所以只需要记录每个元素的左边最小值leftMin[i]和右边最大值rightMax[i]，满足条件leftMin[i-1]<nums[i]<rightMax[i+1]即可。辅助空间：O(n)
2.为了较低空间复杂度，采用双指针遍历一次：
····策略：贪心算法
对于一个low1 mid1 序列，num[i]无法构成的序列对于更小的low2 mid2可能构成；所以要尽量将low mid 压缩到最低，可以发现：更新low的时候，满足条件的num[i]>mid判断不受low影响；如果更新mid，更不受影响了，因为是从左向右遍历的；
首先，如果对于一个序列low mid 只有当num[i]>mid 就构成了升序序列；
1.如果num[i]<low，那么num=low,即使num[i]在前面，但当num[i]>mid时，也一定大于前面的low
2.如果num[i]>low且num[i]<mid,令mid=num[i]，更新了更小的mid(根据贪心，更容易实现)
3.如果num[i]>mid.则满足条件,输出；
····原题链接：https://leetcode.cn/problems/increasing-triplet-subsequence/?favorite=2ckc81c

1.题目如下：

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

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true

解释：任何 i < j < k 的三元组都满足题意

示例 2：

输入：nums = [5,4,3,2,1]
输出：false

解释：不存在满足题意的三元组

示例 3：

输入：nums = [2,1,5,0,4,6]
输出：true

解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

2.代码如下：

class Solution {
public:
//思路一：数组遍历 空间复杂度O(n)
/*
    用两个数组，来记录每一个元素未知的左边最小值和右边最大值；
    对于nums[i]，如果由min[i-1]<nums[i] 且max[i+1]>nums[i]，则满足条件
*/
/*
    bool increasingTriplet(vector<int>& nums) {
        vector<int> leftMin(nums.size(),0);
        vector<int> rightMax(nums.size(),0);
        int max1=INT_MIN;
        int min1=INT_MAX;

        for(int i=0;i<nums.size();i++){
            min1=min1<nums[i]?min1:nums[i];
            leftMin[i]=min1;
        }
        for(int i=nums.size()-1;i>=0;i--){
            max1=max1>nums[i]?max1:nums[i];
            rightMax[i]=max1;
        }

        for(int i=1;i<nums.size()-1;i++){
            if(nums[i]>leftMin[i-1] && nums[i]<rightMax[i+1]){
                return true;
            }
        }
        return false;
    }
*/

//思路二：遍历一次
/*
    思路：该贪心算法考虑的是：对于一个low mid 序列，num[i]无法构成的序列对于更小的low mid可能构成；
    所以要尽量将low mid 压缩到最低，可以发现：
    更新low的时候，满足条件的num[i]>mid判断不受low影响；
    如果更新mid，更不受影响了，因为是从左向右遍历的
    
    贪心策略:首先对于一个序列 low mid
    首先，如果对于一个序列low mid  只有当num[i]>mid 就构成了升序序列；
    1.如果num[i]<low，那么num=low,即使num[i]在前面，但当num[i]>mid时，也一定大于前面的low
    2.如果num[i]>low且num[i]<mid,令mid=num[i]，更新了更小的mid(根据贪心，更容易实现)
    3.如果num[i]>mid.则满足条件,输出；


*/

    bool increasingTriplet(vector<int>& nums) {
        int low=INT_MAX;
        int mid=INT_MAX;
        if(nums.size()<3){
            return false;
        }
        for(int i=0;i<nums.size();i++){
            //满足条件
            if (nums[i]>mid) {
                return true;
            //更新mid
            } else if(nums[i]>low) {
                mid=nums[i];
            //更新low
            } else {
                low=nums[i];
            }
        }
        return false;
    }

};