LeetCode 334 Increasing Triplet Subsequence

Tag: 贪心法 LeetCode Posted on 2022-03-08 18:53:48 Edited on 2022-03-08 19:10:18 Views: 122

概述

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

当遇到一个新值时,

  1. 如果其比现有的 a 还小,就用其当 a;
  2. 如果其比现有的 b 还小,就用其当 b;
  3. 否则的话,我们就找到了一个有效解。

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

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/