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