300 最长递增子序列

一、题目

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

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

二、题解

方法一：动态规划

思路：动态规划（DP）。

1. 核心思路

定义状态：

dp[i] 表示 以 nums[i] 结尾 的最长递增子序列长度。

由于每个元素本身都可以构成一个长度为 1 的递增子序列，因此：

dp[i] = 1;

对于当前元素 nums[i]，遍历它之前所有元素：

如果

nums[j] < nums[i]

说明可以把 nums[i] 接到 nums[j] 后面。

因此有状态转移：

dp[i] = Math.max(dp[i], dp[j] + 1);

最后所有 dp[i] 中最大的值就是答案。

2. 具体步骤

  1. 定义 dp 数组，初始化全部为 1。
  2. 从左到右遍历数组。
  3. 对于每个位置 i，遍历前面的所有位置 j。
  4. 如果 nums[j] < nums[i]，更新 dp[i]。
  5. 遍历过程中维护最大值并返回。

3. 关键逻辑

if (nums[j] < nums[i]) {
    dp[i] = Math.max(dp[i], dp[j] + 1);
}

解释：

  • 如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 后面；
  • 此时递增子序列长度增加 1；
  • 更新以 nums[i] 结尾的最长递增子序列长度。

4. 代码

import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {

        int n = nums.length;

        // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
        int[] dp = new int[n];

        // 每个元素至少可以组成长度为1的递增子序列
        Arrays.fill(dp, 1);

        int ans = 1;

        for (int i = 1; i < n; i++) {

            for (int j = 0; j < i; j++) {

                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }

            }

            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }
}

5. 复杂度分析

时间复杂度：O(n²)

说明：对于每个元素，都需要遍历前面的所有元素。

空间复杂度：O(n)

说明：使用了一个长度为 n 的 dp 数组。

方法二：贪心 + 二分查找

思路：贪心 + 二分查找。

1. 核心思路

维护一个数组 tails：

tails[i] 表示 长度为 i+1 的递增子序列，其结尾元素的最小值。

注意：

tails 并不是最长递增子序列本身，而是为了保证后续能够接更多数字，因此始终让结尾尽可能小。

对于每个数字：

  • 如果比当前所有结尾都大，直接追加；
  • 否则利用二分查找找到第一个大于等于它的位置进行替换。

最终：

tails.length

就是最长递增子序列长度。

2. 具体步骤

  1. 创建 tails 数组。
  2. 遍历数组中的每个元素。
  3. 二分查找第一个大于等于当前数字的位置。
  4. 找到则替换，否则追加。
  5. 返回 tails 的有效长度。

3. 关键逻辑

while (left < right) {

    int mid = left + (right - left) / 2;

    if (tails[mid] < num) {
        left = mid + 1;
    } else {
        right = mid;
    }
}

tails[left] = num;

if (left == len) {
    len++;
}

解释：

  • 如果 tails[mid] < num，说明当前位置还能继续向右寻找；
  • 否则说明当前位置可以作为替换位置；
  • 找到第一个大于等于 num 的位置后进行替换；
  • 如果替换位置正好等于当前长度，则说明可以扩展新的递增子序列。

4. 代码

class Solution {

    public int lengthOfLIS(int[] nums) {

        int[] tails = new int[nums.length];

        int len = 0;

        for (int num : nums) {

            int left = 0;
            int right = len;

            // 二分查找第一个 >= num 的位置
            while (left < right) {

                int mid = left + (right - left) / 2;

                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            tails[left] = num;

            // 如果插入到了末尾，说明长度增加
            if (left == len) {
                len++;
            }
        }

        return len;
    }
}

5. 复杂度分析

时间复杂度：O(n log n)

说明：每个元素进行一次二分查找。

空间复杂度：O(n)

说明：使用了一个 tails 数组。

评论