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;
    }

};