题目描述
题目链接: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