力扣11.23

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.length
• 1 <= n <= 105
• 1 <= 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 <= 105
• 1 <= 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 <= 1000
• scores.length == ages.length
• <= scores[i] <= 106
• 1 <= ages[i] <= 1000

分析

首先将球员先按照年龄排序，再按照分数从小到大排序，令dp[i]表示选择第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 <= 105
• envelopes[i].length == 2
• 1 <= 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;}
};