贪心算法-递增的三页子序列

题目链接

一、问题描述

给定一个整数数组nums，判断是否存在长度为3的递增子序列，即是否存在下标i < j < k，使得nums[i] < nums[j] < nums[k]。

• 存在则返回true，否则返回false。

---

二、核心解法

解法1：动态规划（DP）

• 思路：计算数组的**最长递增子序列（LIS）**的长度，若长度 ≥ 3，则说明存在符合要求的子序列。
• 实现逻辑：
  1. 定义dp[i]表示以nums[i]结尾的最长递增子序列的长度。
  2. 对每个i，遍历所有j < i，若nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j] + 1)。
  3. 遍历dp数组，若存在值 ≥ 3，直接返回true。
• 复杂度：时间复杂度O(n²)，空间复杂度O(n)（需存储dp数组）。

解法2：贪心算法

• 思路：用两个变量a、b分别记录长度为1和长度为2的递增子序列的最小末尾值，遍历数组时更新这两个变量，一旦找到比b大的元素，说明存在长度为3的递增子序列。
• 实现逻辑（以示例[2,1,5,0,4,6]为例）：
  1. 初始化a = ∞，b = ∞。
  2. 遍历每个元素x：
     • 若x ≤ a→ 更新a = x（保持长度1的子序列末尾最小）；
     • 若a < x ≤ b→ 更新b = x（保持长度2的子序列末尾最小）；
     • 若x > b→ 说明存在a < b < x，即长度为3的递增子序列，直接返回true。
  3. 遍历结束未找到则返回false。
• 复杂度：时间复杂度O(n)（仅需一次遍历），空间复杂度O(1)（仅用两个变量），是更优的解法。

---

三、知识点总结

1. 问题本质：该问题是「最长递增子序列（LIS）」的特例，只需判断 LIS 长度是否 ≥ 3。
2. 算法对比：
   • 动态规划适用于需要完整计算 LIS 长度的场景，但时间复杂度较高；
   • 贪心解法针对「判断是否存在长度为3的递增子序列」做了优化，时间、空间效率更优。
3. 贪心策略的核心：维护最小的可能末尾值，让后续更容易找到更长的递增子序列，从而提升效率。