1964. 找出到每个位置为止最长的有效障碍赛跑路线
你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。
对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：
- 你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
- 在这条路线中，必须包含第 i 个障碍。
- 你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
- 除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高
返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。
数据范围
n == obstacles.length1 <= n <= 1051 <= obstacles[i] <= 107
分析
本题数据范围比较大，因此不能使用n方做法，采用贪心+二分的方法，用q数组记录所有长度为i的最长非递减子序列中的最小值，这样可以尽可能多的构造非递减子序列，例如原数组为1，2，3，2
- q=[1]
- q=[1,2]
- q=[1,2,3]
- 2找到第一个大于2的下标，并将其替换q=[1,2,2]，此时替换的位置就是最长序列的长度
代码
class Solution {
public:
const static int N = 1e5 + 5;
int dp[N];
int q[N], tt = -1;
void print() {
for(int i = 0; i <= tt; i ++ ) cout << q[i] << " ";
cout << endl;
}
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
int n = obstacles.size();
vector<int> res;
res.resize(n);
for(int i = 0; i < n; i ++ ) {
if(tt == -1 || obstacles[i] >= q[tt]) {
q[++ tt] = obstacles[i];
res[i] = tt + 1;
}
else {
int pos = upper_bound(q, q + tt, obstacles[i]) - q;
res[i] = pos + 1;
q[pos] = obstacles[i];
}
}
return res;
}
};
2111. 使数组 K 递增的最少操作次数
给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。
如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增 的。
- 比方说，arr = [4, 1, 5, 2, 6, 2] 对于 k = 2 是 K 递增的，因为：
- arr[0] <= arr[2] (4 <= 5)
- arr[1] <= arr[3] (1 <= 2)
- arr[2] <= arr[4] (5 <= 6)
- arr[3] <= arr[5] (2 <= 2)
但是，相同的数组 arr 对于 k = 1 不是 K 递增的（因为 arr[0] > arr[1]），对于 k = 3 也不是 K 递增的（因为 arr[0] > arr[3] ）。
每一次 操作 中，你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。
请你返回对于给定的 k ，使数组变成 K 递增的 最少操作次数 。
数据范围
1 <= arr.length <= 1051 <= arr[i], k <= arr.length
分析
实际就是将原数组拆分为k个子数组，对每个子数组求他的最长非递减子序列，然后对于非递减子序列的元素就是最优的需要修改的，统计一下即可，这里求最长非递减子序列也是通过上题的贪心+二分计算
代码
class Solution {
public:
const static int N = 1e5 + 5;
int dp[N];
int q[N], tt = -1;
void print() {
for(int i = 0; i <= tt; i ++ ) cout << q[tt] << " ";
cout << endl;
}
int kIncreasing(vector<int>& arr, int k) {
int res = 0;
int n = arr.size();
for(int i = 0; i <= k - 1; i ++ ) {
tt = -1;
int cnt = 0;
for(int j = i; j < n; j += k) {
cnt ++ ;
if(tt == -1 || arr[j] >= q[tt]) q[++ tt] = arr[j];
else {
int pos = upper_bound(q, q + tt, arr[j]) - q;
q[pos] = arr[j];
}
}
res += cnt - (tt + 1);
}
return res;
}
};
1626. 无矛盾的最佳球队
假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。
然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数
数据范围
1 <= scores.length, ages.length <= 1000scores.length == ages.length<= scores[i] <= 1061 <= ages[i] <= 1000
分析
首先将球员先按照年龄排序，再按照分数从小到大排序，令dp[i]表示选择第i个球员的最大分数，状态转移如下：
- d p [ i ] = m a x ( d p [ i ] , d p [ j ] + s c o r e [ i ] ) dp[i]=max(dp[i],dp[j]+score[i]) dp[i]=max(dp[i],dp[j]+score[i])
代码
class Solution {
public:
const static int N = 1005;
int dp[N], agedp[N];
struct node_ {
int score, age;
friend bool operator < (const node_ a, const node_ b) {
if(a.age == b.age) return a.score < b.score;
return a.age < b.age;
}
};
vector<node_> nodes;
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = ages.size();
for(int i = 0; i < n; i ++ ) {
nodes.push_back({scores[i], ages[i]});
}
sort(nodes.begin(), nodes.end());
for(int i = 0; i < n; i ++ ) {
dp[i] += nodes[i].score;
for(int j = 0; j < i; j ++ ) {
if(nodes[j].score <= nodes[i].score) dp[i] = max(dp[i], dp[j] + nodes[i].score);
}
}
int res = 0;
for(int i = 0; i < n; i ++ ) res = max(res, dp[i]);
return res;
}
};
54. 俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
数据范围
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105
分析
先按w升序，再按h降序，按h降序保证了w相同的信封只能选一个，然后对h求最长上升子序列就行，此时就满足h递增且w递增
代码
class Solution {
public:
const static int N = 1e5 + 5;
struct node_ {
int a, b;
friend bool operator < (const node_ &a, const node_ &b) {
if(a.a == b.a) return a.b > b.b;
return a.a < b.a;
}
};
int n;
node_ q[N];
int tt = -1;
vector<node_> envelopes;
int find(node_ x) {
int l = 0, r = tt;
while(l < r) {
int mid = (l + r) >> 1;
if(q[mid].b < x.b) l = mid + 1;
else r = mid;
}
return l;
}
int maxEnvelopes(vector<vector<int>>& envs) {
n = envs.size();
for(int i = 0; i < n; i ++ ) envelopes.push_back({envs[i][0], envs[i][1]});
sort(envelopes.begin(), envelopes.end());
for(int i = 0; i < n; i ++ ) {
int a = envelopes[i].a, b = envelopes[i].b;
if(tt == -1 || b > q[tt].b) q[++ tt] = {a, b};
else {
int pos = find({a, b});
q[pos] = {a, b};
}
}
return tt + 1;
}
};
