300.longest-increasing-subsequence

发表评论
361 views

 ›
300.longest-increasing-subsequence

300. 最长上升子序列

给定一个无序的整数数组, 找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101], 它的长度是 4。

说明:

可能会有多种最长上升子序列的组合, 你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

思路

  1. 暴力 O(2^n)
  2. DP 复杂度 O(n^2)
  • a. DP[i] 从第一个元素开始, 到 第 i 个元素(包含第 i 个)的最长上升子序列
    结果为 max(dp[0], dp[1], ... ,dp[n-1])
  • b. 伪代码
for i: 0-> n-1:
    dp[i] = max(dp[j] + 1) # j: 0->i-1 且 a[j] < a[i], 等价于 dp[i] = max(dp[j]) + 1
  1. 二分法 O(NlogN)
  • a. 维护数组 LIS, 最终结果为 LIS 数组的长度
  • b. 伪代码
for i: 0 -> n-1:
    IIS 为空或者第 i 个元素 比 LIS 数组中所有元素都大, 则append 到数组末尾  
    否则(用二分法查找)替换 LIS 数组中比 第 i 个元素大的数中的最小的数

解法一

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int result = 1;
        int[] dp = new int[nums.length];
        // for (int i = 0; i < nums.length; i++) dp[i] = 1;
        Arrays.fill(dp, 1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) 
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

解法二

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> res;
        for (int i = 0; i < nums.size();i++) {
            auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
            if (it == res.end()) res.push_back(nums[i]); // 增加元素数组
            else *it = nums[i]; // 替换
        }
        return res.size();
    }
};