NC91. 最长上升子序列(三)
描述
示例1
输入:
[2,1,5,3,6,4,8,9,7]
输出:
[1,3,4,8,9]
示例2
输入:
[1,2,8,6,4]
输出:
[1,2,4]
说明:
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）C++ 解法, 执行用时: 18ms, 内存消耗: 3860KB, 提交时间: 2021-09-08
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
vector<int> LIS(vector<int>& arr) {
int n = arr.size();
vector<int> d(n + 1, -1), p(n);
int len = 1;//初始化长度为1，元素为序列第一个数字
d[len] = arr[0];
p[0] = 1;
for(int i = 1; i < n; ++i) {
if(arr[i] > d[len]) {
//此时将该数字添加到末尾
d[++len] = arr[i];
p[i] = len;
} else {
//二分查找恰好合适的位置
int left = 1, right = len, pos = 0;
while(left <= right) {
int mid = (left + right) / 2;
if(d[mid] < arr[i]) {
pos = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
//对该位置数字进行更新
d[pos + 1] = arr[i];
p[i] = pos + 1;
}
}
vector<int> ans(len);
//逆向查找对应序列值
for(int i = n - 1; i >= 0; --i) {
if(p[i] == len) {
ans[--len] = arr[i];
}
}
return ans;
}
};
C++ 解法, 执行用时: 19ms, 内存消耗: 4828KB, 提交时间: 2021-12-12
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* retrun the longest increasing subsequence
* @param arr int整型vector the array
* @return int整型vector
*/
vector<int> LIS(vector<int>& arr) {
vector<int> maxLen,res;
if(arr.empty())
return res;
maxLen.emplace_back(1);
res.emplace_back(arr[0]);
int n=arr.size();
int i,j;
for(i=1;i<n;++i){
if(arr[i]>res.back()){
res.emplace_back(arr[i]);
maxLen.emplace_back(res.size());
}
else{
//查找大于等于arr[i]的第一个元素
int pos=lower_bound(res.begin(),res.end(),arr[i])-res.begin();
res[pos]=arr[i];
maxLen.emplace_back(pos+1);
}
}
for(i=n-1,j=res.size();i>=0&&j>=1;--i){
if(maxLen[i]==j){
res[--j]=arr[i];
}
}
return res;
}
};
C++ 解法, 执行用时: 20ms, 内存消耗: 3876KB, 提交时间: 2021-09-24
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
vector<int> LIS(vector<int>& arr) {
int n = arr.size();
vector<int> d(n + 1, -1), p(n);
if (arr.size() >= 200000) return d;
int len = 1;//初始化长度为1，元素为序列第一个数字
d[len] = arr[0];
p[0] = 1;
for(int i = 1; i < n; ++i) {
if (arr[i] >= 1000000000) return d;
if(arr[i] > d[len]) {
//此时将该数字添加到末尾
d[++len] = arr[i];
p[i] = len;
} else {
//二分查找恰好合适的位置
int left = 1, right = len, pos = 0;
while(left <= right) {
int mid = (left + right) / 2;
if(d[mid] < arr[i]) {
pos = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
//对该位置数字进行更新
d[pos + 1] = arr[i];
p[i] = pos + 1;
}
}
vector<int> ans(len);
//逆向查找对应序列值
for(int i = n - 1; i >= 0; --i) {
if(p[i] == len) {
ans[--len] = arr[i];
}
}
return ans;
}
};
C++ 解法, 执行用时: 21ms, 内存消耗: 3888KB, 提交时间: 2022-03-24
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* retrun the longest increasing subsequence
* @param arr int整型vector the array
* @return int整型vector
*/
vector<int> LIS(vector<int>& arr) {
vector<int> maxLen,res;
if(arr.empty())
return res;
maxLen.emplace_back(1);
res.emplace_back(arr[0]);
int n=arr.size();
int i,j;
for(i=1;i<n;++i){
if(arr[i]>res.back()){
res.emplace_back(arr[i]);
maxLen.emplace_back(res.size());
}
else{
//查找大于等于arr[i]的第一个元素
int pos=lower_bound(res.begin(),res.end(),arr[i]) - res.begin();
res[pos]=arr[i];
maxLen.emplace_back(pos+1);
}
}
vector<int> temp(res.size(), 0);
for(i=n-1,j=res.size();i>=0;--i){
if(maxLen[i]==j){
temp[--j]=arr[i];
}
}
return temp;
}
};
C++ 解法, 执行用时: 22ms, 内存消耗: 3956KB, 提交时间: 2022-05-06
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* retrun the longest increasing subsequence
* @param arr int整型vector the array
* @return int整型vector
*/
vector<int> LIS(vector<int> &A) {
if (A.empty())
return vector<int>();
int N = A.size(), topSize = 1;
vector<int> top(N, 0), topIndexes(N, 0), pre(N, 0);
top[0] = A[0];
for (int i = 1; i < N; i++) {
if (A[i] > top[topSize - 1]) {
pre[i] = topIndexes[topSize - 1];
top[topSize] = A[i];
topIndexes[topSize++] = i;
} else {
int pos = lower_bound(top.begin(), top.begin() + topSize, A[i]) - top.begin();
if (pos)
pre[i] = topIndexes[pos - 1];
top[pos] = A[i];
topIndexes[pos] = i;
}
}
int endIndex = topIndexes[topSize - 1];
vector<int> seq(topSize, 0);
for (int i = topSize - 1, s = endIndex; i >= 0; i--, s = pre[s]) {
seq[i] = A[s];
}
return seq;
}
};