LeetCode 334.递增的三元子序列

内容纲要

题目链接
题目描述:给你一个整数数组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 * 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
    进阶:你能实现时间复杂度为O(n),空间复杂度为O(1)的解决方案吗?

解法一:双向遍历
解析

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return false;
        // lmin[i]:表示nums[0]到nums[i]中的最小值;
        // rmax[i]:表示nums[i]到nums[n-1]中的最大值。
        int lmin[n], rmax[n];
        lmin[0] = nums[0];
        for (int i = 1; i < n; i++) lmin[i] = min(lmin[i - 1], nums[i]);
        rmax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) rmax[i] = max(rmax[i + 1], nums[i]);
        for (int i = 1; i < n - 1; i++) 
            if (lmin[i - 1] < nums[i] && nums[i] < rmax[i + 1]) 
                return true;
        return false;
    }
};

解法二:贪心
解析

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return false;
        int first = nums[0], second = INT_MAX;
        for (int x : nums) {
            if (x <= first) first = x;
            else if (x <= second) second = x;
            else return true;
        }
        return false;
    }
};

《LeetCode 334.递增的三元子序列》上有2条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注