当前位置：首页 > news >正文

LeetCode 300 最长递增子序列

news 2025/6/6 15:34:10

https://leetcode.cn/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=selected-coding-interview

方法一：动态规划（基础解法）

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;vector<int> dp(n, 1);  // dp[i] 表示以nums[i]结尾的LIS长度int maxLen = 1;for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);}}maxLen = max(maxLen, dp[i]);  // 更新全局最大值}return maxLen;}
};

方法二：贪心 + 二分查找解法

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> tails;  // tails[k] 表示长度为k+1的LIS的末尾最小元素for (int num : nums) {// 二分查找第一个 >= num 的位置auto it = lower_bound(tails.begin(), tails.end(), num);if (it == tails.end()) {tails.push_back(num);  // 可以扩展LIS长度} else {*it = num;  // 替换为更小的末尾元素}}return tails.size();}
};

这段代码是贪心 + 二分查找解法的核心逻辑，用于维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的末尾最小元素。以下是对 if (it == tails.end()) 条件的详细解释：

1. `lower_bound` 的作用

auto it = lower_bound(tails.begin(), tails.end(), num);

功能：在有序数组 tails 中查找第一个大于等于 num 的元素位置。
返回值：
- 若存在这样的元素，返回其迭代器；
- 若不存在（即 num 大于所有元素），返回 tails.end()。

2. 条件判断逻辑

情况一：`it == tails.end()`

含义：num 大于 tails 中的所有元素。
操作：tails.push_back(num)。
意义：
- 可以形成一个更长的递增子序列。例如：
  - 若 tails = [2, 3, 7]，当前 num = 101，则 101 可接在 7 后面，形成长度为 4 的子序列 [2, 3, 7, 101]。
- tails 的长度直接增加 1，对应最长递增子序列的长度加 1。

情况二：`it != tails.end()`

含义：tails 中存在第一个大于等于 num 的元素，记为 tails[i]。
操作：*it = num（等价于 tails[i] = num）。
意义：
- 用更小的 num 替换 tails[i]，使得后续元素更容易扩展出更长的子序列。例如：
  - 若 tails = [2, 3, 7, 101]，当前 num = 18，则 18 < 101，用 18 替换 101 后，tails 变为 [2, 3, 7, 18]。
  - 这样，未来若有元素 20，可以接在 18 后面形成长度为 4 的子序列，而原来的 101 可能无法容纳更小的后续元素。
- 贪心策略：在保持子序列长度不变的前提下，尽可能让末尾元素更小，为后续扩展留有余地。

3. 举例说明

以输入 nums = [2, 5, 3, 7, 101, 18] 为例，看 tails 的变化过程：

处理 2：
- tails 为空，lower_bound 返回 end，tails.push_back(2) → tails = [2]。
处理 5：
- lower_bound 找到 2 < 5，返回 end，tails.push_back(5) → tails = [2, 5]。
处理 3：
- lower_bound 在 [2,5] 中查找第一个 ≥3 的元素，找到 5（索引 1）。
- 用 3 替换 5 → tails = [2, 3]。此时长度仍为 2，但末尾元素更小。
处理 7：
- lower_bound 返回 end，tails.push_back(7) → tails = [2, 3, 7]。
处理 101：
- lower_bound 返回 end，tails.push_back(101) → tails = [2, 3, 7, 101]。
处理 18：
- lower_bound 在 [2,3,7,101] 中查找第一个 ≥18 的元素，找到 101（索引 3）。
- 用 18 替换 101 → tails = [2, 3, 7, 18]。此时长度仍为 4，但末尾元素更小，有利于后续扩展。

4. 为什么这样做能得到正确结果？

tails 的性质：
tails 始终是递增数组（因为每次添加元素都在末尾，替换操作也不会破坏递增顺序）。
长度的正确性：
tails 的长度始终等于当前最长递增子序列的长度。因为每次 push_back 都会增加长度，而替换操作不会改变长度。
末尾元素的最优性：
对于每个可能的长度 k，tails[k-1] 是所有长度为 k 的递增子序列中末尾最小的元素，这使得后续元素更容易形成更长的子序列。