贪心算法：300.最长递增子序列

300. 最长递增子序列

问题描述

给定一个整数数组 nums，找到其中最长的严格递增子序列的长度。

算法思路

贪心策略结合二分查找。维护一个数组 dp，其中 dp[i] 表示长度为 i+1 的递增子序列的最小末尾元素。遍历原数组，若当前元素大于 dp 末尾，则扩展；否则用二分查找替换 dp 中第一个大于等于当前元素的位置，以保持 dp 的单调性。

代码实现

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> dp;
        dp.push_back(nums[0]);
        for (int i = 1; i < n; i++) {
            if (nums[i] > dp.back()) {
                dp.push_back(nums[i]);
            } else {
                int left = 0, right = dp.size();
                while (left < right) {
                    int mid = (left + right) >> 1;
                    if (nums[i] > dp[mid]) left = mid + 1;
                    else right = mid;
                }
                dp[left] = nums[i];
            }
        }
        return dp.size();
    }
};

复杂度分析

• 时间复杂度：O(N log N)，其中 N 为数组长度。每个元素最多进行一次二分查找。
• 空间复杂度：O(N)，用于存储 dp 数组。