LeetCode 334 Increasing Triplet Subsequence

    
        标签：
        
            贪心法
        
            LeetCode
        
    发布于：2022-03-08 18:53:48
    编辑于：2022-03-08 19:10:18
    浏览量：1097

概述

https://leetcode.com/problems/increasing-triplet-subsequence/

暴力遍历法

时间复杂度 O(n^3)：

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if (nums.size() < 3) return false;
        for (int i = 0; i < nums.size(); i ++) {
            for (int j = i + 1; j < nums.size(); j ++) {
                if (nums[i] >= nums[j]) continue;
                for (int k = j + 1; k < nums.size(); k ++) {
                    if (nums[j] >= nums[k]) continue;
                    return true;
                }
            }
        }
        return false;
    }
};

果然 TLE。

缓存之后的最大值

构造缓存，记录 i 之后的最大值。

时间复杂度优化到 O(n^2)，依旧超时：

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if (nums.size() < 3) return false;
        auto maxs = nums;
        int maxv = INT_MIN;
        for (int i = nums.size() - 1; i >= 0; i --) {
            maxv = max(maxv, nums[i]);
            maxs[i] = maxv;
        }
        
        for (int i = 0; i < nums.size(); i ++) {
            for (int j = i + 1; j < nums.size(); j ++) {
                if (nums[i] >= nums[j]) continue;
                if (maxs[j] > nums[j]) return true;
            }
        }
        return false;
    }
};

实际上，遍历 i 时有些值可以不必再遍历，如果之前已经出现比其还小的值的话。因为如果之前更小的值都不行，那现在不仅可选择项可小肯定也不行。

进行该项优化后 AC 了：

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if (nums.size() < 3) return false;
        auto maxs = nums;
        int maxv = INT_MIN;
        for (int i = nums.size() - 1; i >= 0; i --) {
            maxv = max(maxv, nums[i]);
            maxs[i] = maxv;
        }
        int triedMax = -1;
        for (int i = 0; i < nums.size(); i ++) {
            if (triedMax != -1 && nums[i] >= triedMax) continue;
            for (int j = i + 1; j < nums.size(); j ++) {
                if (nums[i] >= nums[j]) continue;
                if (maxs[j] > nums[j]) return true;
            }
            triedMax = max(triedMax, nums[i]);
        }
        return false;
    }
};

贪心法

https://leetcode.com/problems/increasing-triplet-subsequence/discuss/78993/Clean-and-short-with-comments-C%2B%2B

当遇到一个新值时，

如果其比现有的 a 还小，就用其当 a；
如果其比现有的 b 还小，就用其当 b；
否则的话，我们就找到了一个有效解。

实现的时候注意哦，是小于等于。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int a = INT_MAX, b = INT_MAX;
        for (auto n : nums) {
            if (n <= a) {
                a = n;
            } else if (n <= b) {
                b = n;
            } else {
                return true;
            }
        }
        return false;
    }
};

Links: leetcode-334-increasing-triplet-subsequence