LeetCode 300 最长递增子序列

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 的变化过程：

1. 处理 2：
   • tails 为空，lower_bound 返回 end，tails.push_back(2) → tails = [2]。
2. 处理 5：
   • lower_bound 找到 2 < 5，返回 end，tails.push_back(5) → tails = [2, 5]。
3. 处理 3：
   • lower_bound 在 [2,5] 中查找第一个 ≥3 的元素，找到 5（索引 1）。
   • 用 3 替换 5 → tails = [2, 3]。此时长度仍为 2，但末尾元素更小。
4. 处理 7：
   • lower_bound 返回 end，tails.push_back(7) → tails = [2, 3, 7]。
5. 处理 101：
   • lower_bound 返回 end，tails.push_back(101) → tails = [2, 3, 7, 101]。
6. 处理 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 的递增子序列中末尾最小的元素，这使得后续元素更容易形成更长的子序列。

总结

• if (it == tails.end())：判断当前元素是否能扩展递增子序列的长度，能则添加到末尾。
• else：用当前元素替换 tails 中第一个大于等于它的元素，保证末尾元素尽可能小，为后续扩展留有余地。
• 核心思想：通过贪心策略维护一个最小末尾元素的数组，结合二分查找实现O(nlogn)的高效解法。