标签：ends nums int 递增 pos len vector 序列 最长
最长递增子序列
#include <vector>
using namespace std;
class Solution {
public:
// 时间复杂度 O(n^2)
int lengthOfLIS(vector<int> &nums) {
int n = nums.size();
// dp[i]: 以 nums[i] 结尾的最长递增子序列
vector<int> dp(n);
int res = 0;
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i])
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
return res;
}
};
#include <vector>
using namespace std;
class Solution {
public:
// 大于等于 target 的左边界
int binarySearch(vector<int> &ends, int len, int target) {
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (ends[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
// 时间复杂度 O(n * logn)
int lengthOfLIS(vector<int> &nums) {
int n = nums.size();
// ends[i] 表示所有长度为 i + 1 的递增子序列的最小结尾
// [0, len-1] 是有效区，有效区内的数字一定严格升序
vector<int> ends(n);
// len 表示 ends 数组目前的有效区长度
int len = 0;
for (int i = 0, pos; i < n; ++i) {
pos = binarySearch(ends, len, nums[i]);
if (pos == len) {
// 找不到就扩充 ends
ends[len++] = nums[i];
} else {
// 找到了就更新成更小的 nums[i]
ends[pos] = nums[i];
}
}
return len;
}
};
#include <vector>
using namespace std;
class Solution {
public:
// 大于 target 的左边界
int binarySearch(vector<int> &ends, int len, int target) {
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (ends[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
// 时间复杂度 O(n * logn)
int lengthOfLIS(vector<int> &nums) {
int n = nums.size();
// ends[i] 表示所有长度为 i + 1 的不下降子序列的最小结尾
// [0, len-1] 是有效区，有效区内的数字非递减
vector<int> ends(n);
// len 表示 ends 数组目前的有效区长度
int len = 0;
for (int i = 0, pos; i < n; ++i) {
pos = binarySearch(ends, len, nums[i]);
if (pos == len) {
// 找不到就扩充 ends
ends[len++] = nums[i];
} else {
// 找到了就更新成更小的 nums[i]
ends[pos] = nums[i];
}
}
return len;
}
};
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
// 找大于等于的左边界
int binarySearch(vector<int> &ends, int len, int target) {
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (ends[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
int maxEnvelopes(vector<vector<int>> &envelopes) {
// 宽度从小到大，宽度一样，高度从大到小
sort(begin(envelopes), end(envelopes),
[](vector<int> &v1, vector<int> &v2) {
return v1[0] == v2[0] ? v1[1] > v2[1] : v1[0] < v2[0];
});
int n = envelopes.size();
// ends[i] 表示长度为 i + 1 的子序列的最小末尾元素
// 在有效区内严格递增
vector<int> ends(n);
// ends 数组的有效长度
int len = 0;
for (int i = 0, pos; i < n; ++i) {
int target = envelopes[i][1];
pos = binarySearch(ends, len, target);
if (pos == len) {
// 找不到就扩充 ends
ends[len++] = target;
} else {
// 找到了就更新成更小的 nums[i]
ends[pos] = target;
}
}
return len;
}
};
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
// 大于 target 的左边界
int binarySearch(vector<int> &ends, int len, int target) {
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (ends[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
// 时间复杂度 O(n * logn)
int lengthOfLIS(vector<int> &nums) {
int n = nums.size();
// ends[i] 表示所有长度为 i + 1 的不下降子序列的最小结尾
// [0, len-1] 是有效区，有效区内的数字非递减
vector<int> ends(n);
// len 表示 ends 数组目前的有效区长度
int len = 0;
for (int i = 0, pos; i < n; ++i) {
pos = binarySearch(ends, len, nums[i]);
if (pos == len) {
// 找不到就扩充 ends
ends[len++] = nums[i];
} else {
// 找到了就更新成更小的 nums[i]
ends[pos] = nums[i];
}
}
return len;
}
int kIncreasing(vector<int> &arr, int k) {
int n = arr.size();
int res = 0;
// 分为 k 组
for (int i = 0; i < k; ++i) {
vector<int> temp;
for (int j = i; j < n; j += k)
temp.emplace_back(arr[j]);
// 累加这一组需要修改的数字
res += temp.size() - lengthOfLIS(temp);
}
return res;
}
};
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int binarySearch(vector<int> &ends, int len, int target) {
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (ends[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
int findLongestChain(vector<vector<int>> &pairs) {
// 按照数对中第一个数增序
sort(begin(pairs), end(pairs),
[](vector<int> &v1, vector<int> &v2) {
return v1[0] < v2[0];
});
int n = pairs.size();
vector<int> ends(n);
int len = 0;
for (int i = 0, pos; i < n; ++i) {
// 根据数对中第一个数字查
pos = binarySearch(ends, len, pairs[i][0]);
if (pos == len) {
// 插入的是数对中的第二个数字
ends[len++] = pairs[i][1];
} else {
// 改成较小的
ends[pos] = min(ends[pos], pairs[i][1]);
}
}
return len;
}
};
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int n, k;
// 求最长不上升子序列长度的二分
// ends[0, len - 1] 为降序，找小于 target 的最左位置
int binarySearch1(vector<int> &ends, int len, int target) {
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (ends[mid] < target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
// 求最长不下降子序列长度的二分
// ends[0, len-1] 为升序，找大于 target 的最左位置
int binarySearch2(vector<int> &ends, int len, int target) {
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (ends[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
// 生成辅助数组 rightMaxLen
// rightMaxLen[i]: 以 nums[i] 开头的最长不下降子序列长度
// 等价于从右往左遍历，以 nums[i] 做结尾的情况下的最长不上升子序列
vector<int> getRightMaxLen(vector<int> &ends, vector<int> &nums) {
vector<int> rightMaxLen(nums.size());
int len = 0;
for (int i = n - 1, pos; i >= 0; i--) {
pos = binarySearch1(ends, len, nums[i]);
if (pos == len) {
// 扩充 endsArr
ends[len++] = nums[i];
// 记录长度
rightMaxLen[i] = len;
} else {
ends[pos] = nums[i];
rightMaxLen[i] = pos + 1;
}
}
return rightMaxLen;
}
int main() {
cin >> n >> k;
vector<int> nums;
nums.resize(n);
for (int i = 0; i < n; ++i)
cin >> nums[i];
// 生成辅助数组
vector<int> ends(n);
vector<int> rightMaxLen = getRightMaxLen(ends, nums);
int len = 0;
int res = 0;
for (int i = 0, j = k, pos; j < n; i++, j++) {
// 根据当前划分点查，划分点左侧连续 k 个位置是要改成 nums[j] 的
pos = binarySearch2(ends, len, nums[j]);
// res 由三部分组成
// 左侧：划分点左侧连续 k 个位置再往前的区域中，长度为 pos 的不下降子序列（最大值小于 nums[j]）
// 中间：划分点左侧连续 k 个位置
// 右侧：必须以 nums[j] 开始的不下降子序列的长度
res = max(res, pos + k + rightMaxLen[j]);
// 要插入的是 nums[i]，所以要再查找下插入位置
pos = binarySearch2(ends, len, nums[i]);
if (pos == len) {
ends[len++] = nums[i];
} else {
ends[pos] = nums[i];
}
}
// 特例：最后 k 个元素都改成左侧不下降子序列的最后一个值
res = max(res, len + k);
cout << res;
}
标签：ends,
nums,
int,
递增,
pos,
len,
vector,
序列,
最长
From： https://www.cnblogs.com/sprinining/p/18466191