0%

[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),代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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