返回

[Leetcode]300. Longest Increasing Subsequence(C++)

题目描述

题目链接:300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

例子

例子 1

Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

例子 2

Input: nums = [0,1,0,3,2,3] Output: 4

例子 3

Input: nums = [7,7,7,7,7,7,7] Output: 1

Constraints

1 <= nums.length <= 2500 -10^4 <= nums[i] <= 10^4

解题思路

动态规划

用动态规划可以比较直观的求解问题,dp[i] 表示在数组的第 i 位能构建的最长子序列,那么我们只需要对遍历每一个元素 nums[i]时,从头遍历到当前位置的前一位,遇到有比自己小的数 nums[j] 进行更新即可,更新方法为 dp[i] = max(dp[i], dp[j] + 1),代码如下:

#include <vector>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        std::vector<int> maxLenOfLIS(nums.size(), 1);
        int result = 1;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    maxLenOfLIS[i] =
                        std::max(maxLenOfLIS[i], maxLenOfLIS[j] + 1);
                    result = std::max(maxLenOfLIS[i], result);
                }
            }
        }

        return result;
    }
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n)

二分法

二分查找相对来说没有那么好理解,首先理解一个概念,对于相同的递增子序列而言,最后一个元素最小意味着这个序列更有可能被扩展,相对而言也是更优的解(如果我们追求的是获得尽量长的递增子序列),从这个角度来看我们可以构建系统状态如下:

  • dp[i]:表示在当前数组中,能够构建的所有长度为 i 的子序列中最小的末尾元素

我们在遍历数组过程对每一个元素 num 进行以下操作:

  • 如果 num > dp.back():表示 num 比当前能够构建最长的子序列的末尾元素都大,表示我们可以构建一个更大的子序列,所以将其压入 dp 中(由此可以判断 dp 本身是一个递增数组)
  • 否则在 dp 中进行二分查找,找到第一个比 num 大的位置 i,这个位置表明:在 i - 1 以及下的长度能构建的最有子序列的末尾元素比 num 小,而在 i 长度的递增子序列的末尾元素比 num 大,所以我们可以通过将其末尾元素替换为 num 来将其优化:dp[i] = num

代码如下:

#include <vector>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        std::vector<int> lastElementOFLISatLen;
        for (const int num : nums) {
            int index = binary_search(lastElementOFLISatLen, num);
            if (index == lastElementOFLISatLen.size()) {
                lastElementOFLISatLen.push_back(num);
            } else {
                lastElementOFLISatLen[index] = num;
            }
        }

        return lastElementOFLISatLen.size();
    }

private:
    int binary_search(const std::vector<int>& nums, int target) {
        if (nums.empty() || nums.back() < target) return nums.size();
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
};
  • 时间复杂度: O(n logn)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 300.LongestIncreasingSubsequence.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy