A. 2418. 按身高排序
题目描述：
给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。
对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。
请按身高 降序 顺序返回对应的名字数组 names 。
AC代码：
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
map<int, string> m;
for (int i = 0; i < heights.size(); i ++)
m[heights[i]] = names[i];
vector<string> ans;
for (auto it = m.begin(); it != m.end(); it ++)
ans.push_back(it -> second);
reverse(ans.begin(), ans.end());
return ans;
}
};B. 2419. 按位与最大的最长子数组
题目描述：
给你一个长度为 n 的整数数组 nums 。
考虑 nums 中进行 按位与（bitwise AND）运算得到的值 最大 的 非空 子数组。
- 换句话说，令 k 是 nums 任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 k 的子数组。
返回满足要求的 最长 子数组的长度。
- 数组的按位与就是对数组中的所有数字进行按位与运算。 子数组 是数组中的一个连续元素序列。
思维题，子数组按位与的结果一定小于子数组的最大值，所以最大的与值一定是数组的最大值，然后我们检查一下这个最大值连续出现的最大长度即可。
AC代码：
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int maxn = -1e6;
for (auto c : nums)
maxn = max(maxn, c);
int ans = 0, c = 0;
for (int i = 0; i < nums.size(); i ++)
{
if (nums[i] == maxn) c ++;
else c = 0;
ans = max(ans, c);
}
return ans;
}
};C. 2420. 找到所有好下标
题目描述：
给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。
对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：下标 i 之前 的 k 个元素是 非递增的 。
下标 i 之后 的 k 个元素是 非递减的 。
按 升序 返回所有好下标。
- 先预处理出
up、down数组。
-
up[i]:记录i右边(包括i)连续递增的数列个数。 -
down[i]:记录i左边(包括i)连续递增的数列个数。
- 直接枚举符合
k <= i < n - k条件的i。
AC代码：
class Solution {
public:
vector<int> goodIndices(vector<int>& nums, int k) {
int len = nums.size();
vector<int> ans, down(len, 1), up(len, 1);
if (len <= 2 * k) return ans;
for (int i = 1; i < len; i ++)
if (nums[i - 1] >= nums[i])
down[i] = down[i - 1] + 1;
for (int i = len - 2; i >= 0; i --)
if (nums[i + 1] >= nums[i])
up[i] = up[i + 1] + 1;
for (int i = k; i < len - k; i ++)
if (down[i - 1] >= k && up[i + 1] >= k)
ans.push_back(i);
return ans;
}
};D. 2421. 好路径的数目
题目描述：
给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。
给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
一条 好路径 需要满足以下条件：
开始节点和结束节点的值 相同 。
开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。
请你返回不同好路径的数目。
注意，一条路径和它反向的路径算作 同一 路径。比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。
AC代码：
class Solution {
public:
vector<int> fa;
int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
int n = vals.size();
vector<vector<int>> g(n);
for (auto &e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
vector<int> id(n), size(n, 1);
fa.resize(n);
// 并查集初始化操作
// 单个节点也算为一条合法的路径
for (int i = 0; i < n; i ++) id[i] = i, fa[i] = i;
sort(id.begin(), id.end(), [&](int a, int b){
return vals[a] < vals[b];
});
int ans = n;
// 从小到大遍历
for (auto u : id) {
for (auto c : g[u]) {
// 邻居节点vals大的当前不合并。
if (vals[c] > vals[u]) continue;
// 找到这两个集合的代表元，注意pu节点的节点值一定是vals[u]，vals[u]是当前访问过所有节点的最大val
int fu = find(u), fc = find(c);
// 属于同一个连通块不需要再次计算
if (fu == fc) continue;
// 如果值相等，就说明开始节点和结束节点的值相等，那么就可以合并。
if (vals[fu] == vals[fc]) {
ans += size[fu] * size[fc]; // 乘法原理。因为pu连通块最大值节点与pc连通块最大值节点相连，路径上的节点值都小于等于最大值.
size[fu] += size[fc];
}
fa[fc] = fu;//按照节点值从小到大遍历，pu的节点值是vals[u]是当前最大的，所以pc合并到pu
}
}
return ans;
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
};