第432场周赛：跳过交替单元格的之字形遍历、机器人可以获得的最大金币数、图的最大边权的最小值、统计 K 次操作以内得到非递减子数组的数目
Q1、跳过交替单元格的之字形遍历
1、题目描述
给你一个 m x n 的二维数组 grid，数组由 正整数 组成。
你的任务是以 之字形 遍历 grid，同时跳过每个 交替 的单元格。
之字形遍历的定义如下：
- 从左上角的单元格
(0, 0)开始。 - 在当前行中向 右 移动，直到到达该行的末尾。
- 下移到下一行，然后在该行中向 左 移动，直到到达该行的开头。
- 继续在行间交替向右和向左移动，直到所有行都被遍历完。
**注意：**在遍历过程中，必须跳过每个 交替 的单元格。
返回一个整数数组 result，其中包含按 顺序 记录的、且跳过交替单元格后的之字形遍历中访问到的单元格值。
2、解题思路
-
方向交替：
- 遍历过程中，偶数行从左到右，奇数行从右到左。可以使用
reverse方法在遍历奇数行时反转数组。
- 遍历过程中，偶数行从左到右，奇数行从右到左。可以使用
-
跳过单元格：
-
通过布尔变量
flag来控制是否访问当前单元格。 -
每访问一个单元格后，将
flag取反，跳过下一个单元格。
-
-
结果记录：
- 将每次访问到的单元格值存入结果数组
ret中。
- 将每次访问到的单元格值存入结果数组
3、代码实现
class Solution {
public:
vector<int> zigzagTraversal(vector<vector<int>>& grid) {
vector<int> ret; // 存储最终结果数组
bool flag = true; // 标记是否访问当前单元格, 初始为访问
// 遍历每一行
for (int i = 0; i < grid.size(); ++i) {
// 当前行的引用, 便于操作
auto& row = grid[i];
// 奇数行需要反转以实现从右到左的遍历
if (i % 2 == 1) {
ranges::reverse(row); // 使用 C++20 的 ranges::reverse 反转行
}
// 遍历当前行的所有元素
for (int x : row) {
// 如果标记为 true, 则访问当前单元格
if (flag) {
// 将当前单元格值加入结果数组
ret.push_back(x);
}
// 取反标记, 跳过下一个单元格
flag = !flag;
}
}
return ret; // 返回最终结果
}
};
4、复杂度分析
时间复杂度分析
- 行遍历：
- 外层
for循环遍历所有m行。
- 外层
- 行内遍历：
- 每行遍历 n 个元素，共访问 m × n m\times n m×n 个单元格。
- 奇数行反转操作的复杂度为
O(n)。
总时间复杂度： O ( m × n ) O(m \times n) O(m×n)
空间复杂度分析
- 额外空间：
- 结果数组
ret存储跳过单元格后的值，大小最多为 ⌈ m × n / 2 ⌉ \lceil m \times n / 2 \rceil ⌈m×n/2⌉。 - 反转操作在原地完成，不需要额外空间。
- 结果数组
总空间复杂度： O ( m × n ) O(m \times n) O(m×n)（存储结果数组的空间）
Q2、机器人可以获得的最大金币数
1、题目描述
给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发，目标是到达网格的右下角 (m - 1, n - 1)。在任意时刻，机器人只能向右或向下移动。
网格中的每个单元格包含一个值 coins[i][j]：
- 如果
coins[i][j] >= 0，机器人可以获得该单元格的金币。 - 如果
coins[i][j] < 0，机器人会遇到一个强盗，强盗会抢走该单元格数值的 绝对值 的金币。
机器人有一项特殊能力，可以在行程中 最多感化 2个单元格的强盗，从而防止这些单元格的金币被抢走。
**注意：**机器人的总金币数可以是负数。
返回机器人在路径上可以获得的 最大金币数 。
2、解题思路
我们可以使用动态规划 (Dynamic Programming, DP) 来解决问题。采用一个三维 dp 数组，其中 dp[i][j][k] 表示机器人到达网格单元 (i, j) 时，感化了 k 个强盗后能够获得的最大金币数。
动态规划转移方程
-
定义状态
dp[i][j][k]：到达单元(i, j)，感化了k个强盗后的最大金币数。k的范围为[0, 2]，表示机器人最多能感化 2 个强盗。
-
状态转移
- 假设当前单元格的金币值为
coins[i][j]：- 如果从 上方
(i-1, j)转移到(i, j)：- 如果不感化强盗，
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k] + coins[i][j])。 - 如果感化强盗（即
coins[i][j] < 0且剩余感化次数k > 0），dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1])。
- 如果不感化强盗，
- 如果从 左侧
(i, j-1)转移到(i, j)：- 与从上方的情况类似。
- 如果从 上方
- 假设当前单元格的金币值为
-
初始条件
- 对于起点
(0, 0)：- 如果
coins[0][0] >= 0，金币数为coins[0][0]。 - 如果
coins[0][0] < 0且感化强盗次数k > 0，金币数为0（感化该强盗）。
- 如果
- 对于起点
-
最终结果
-
机器人到达右下角
(m-1, n-1)时，可能感化了 0、1 或 2 个强盗。最终答案为：max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])
-
3、代码实现
class Solution {
public:
int maximumAmount(vector<vector<int>>& coins) {
int m = coins.size(); // 网格的行数
int n = coins[0].size(); // 网格的列数
// 定义 DP 数组: dp[i][j][k] 表示到达 (i, j) 感化了 k 个强盗后的最大金币数
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, INT_MIN)));
// 初始化起点
for (int k = 0; k <= 2; ++k) {
dp[0][0][k] = (coins[0][0] < 0 && k > 0) ? 0 : coins[0][0];
}
// 动态规划填表
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 遍历感化强盗的次数 k
for (int k = 0; k <= 2; ++k) {
// 跳过起点
if (i == 0 && j == 0) {
continue;
}
int coinValue = coins[i][j]; // 当前单元格的金币值
// 从上方到达当前单元格 (i, j)
if (i > 0) {
if (coinValue >= 0) {
// 当前单元格是正值, 直接加金币
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + coinValue);
} else {
// 当前单元格是负值, 分两种情况讨论
dp[i][j][k] =max(dp[i][j][k], dp[i - 1][j][k] + coinValue); // 不感化强盗
if (k > 0) {
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1]); // 感化强盗
}
}
}
// 从左侧到达当前单元格 (i, j)
if (j > 0) {
if (coinValue >= 0) {
dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k] + coinValue);
} else {
dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k] + coinValue);
if (k > 0) {
dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1]);
}
}
}
}
}
}
// 返回到达右下角时感化最多 2 个强盗的最大金币数
return max({dp[m - 1][n - 1][0], dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]});
}
};
4、复杂度分析
时间复杂度
- 三重循环：外层遍历网格的每个单元格，两层内循环遍历感化次数
k，总复杂度为 O ( m × n × 3 ) = O ( m × n ) O(m \times n \times 3) = O(m \times n) O(m×n×3)=O(m×n)。
空间复杂度
- 使用了一个三维数组
dp，大小为 O ( m × n × 3 ) O(m \times n \times 3) O(m×n×3)。
Q3、图的最大边权的最小值
1、题目描述
给你两个整数 n 和 threshold ，同时给你一个 n 个节点的 有向 带权图，节点编号为 0 到 n - 1 。这个图用 二维 整数数组 edges 表示，其中 edges[i] = [Ai, Bi, Wi] 表示节点 Ai 到节点 Bi 之间有一条边权为 Wi的有向边。
你需要从这个图中删除一些边（也可能 不 删除任何边），使得这个图满足以下条件：
- 所有其他节点都可以到达节点 0 。
- 图中剩余边的 最大 边权值尽可能小。
- 每个节点都 至多 有
threshold条出去的边。
请你返回删除必要的边后，最大 边权的 最小值 为多少。如果无法满足所有的条件，请你返回 -1
2、解题思路
本题本质上是一个 图的最短路径问题，但有多个限制条件。我们可以通过以下步骤来思考并解决问题：
-
反向图构建
我们需要从每个节点到达节点0，所以我们构建图的 反向图。反向图中，原本从Ai到Bi的边变为从Bi到Ai的边。这样，我们只需要考虑从节点0到其他节点的路径即可。 -
最大边权最小化
为了确保所有的节点都能到达节点 0，且最大边权最小，我们需要使用 最短路径算法。这里的最短路径的定义是：我们要求路径中的 最大边权最小，这和普通的最短路径问题有些不同。我们可以使用 Dijkstra 算法 来解决这个问题。Dijkstra 算法通常用于找到从起点到所有其他节点的最短路径，而在这个问题中，我们可以将路径的 “最短” 定义为 “最大边权最小”。
-
满足
threshold条件
限制每个节点至多有threshold条出去的边，意味着我们需要在考虑边的同时，保持每个节点的出度不超过threshold。这个限制可以通过构建图时进行检查。 -
最终返回
经过 Dijkstra 算法，我们能够找到从节点 0 到其他所有节点的最大边权。如果所有节点都能到达节点 0，则返回最大边权中的最小值；如果有节点无法到达节点 0，则返回 -1。
3、代码实现
class Solution {
public:
int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
// 如果边小于 n-1, 直接返回 -1 (无法构成连通图)
if (edges.size() < n - 1) {
return -1;
}
// 构建反向图
vector<vector<pair<int, int>>> g(n);
// g[y] 包含 (x, w), 表示 x -> y 的边权为 w
for (const auto& edge : edges) {
int x = edge[0], y = edge[1], w = edge[2];
g[y].emplace_back(x, w);
}
// 初始化距离数组, 初始时所有节点的距离为正无穷
const int INF = numeric_limits<int>::max();
vector<int> dis(n, INF);
dis[0] = 0; // 起点到自身的最大边权为 0
// 最小堆, 存储 (最大边权, 节点编号)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.emplace(0, 0); // 起点
while (!pq.empty()) {
auto [d, x] = pq.top();
pq.pop();
// 如果当前距离大于记录的最小距离, 跳过
if (d > dis[x]) {
continue;
}
// 遍历当前节点的所有入边
for (const auto& [y, w] : g[x]) {
int new_d = max(d, w); // 更新最大边权
// 如果找到更优的路径
if (new_d < dis[y]) {
dis[y] = new_d;
pq.emplace(new_d, y);
}
}
}
// 找到所有节点到达 0 的最大边权值
int ret = *max_element(dis.begin(), dis.end());
return ret == INF ? -1 : ret; // 如果节点无法到达, 返回 -1, 否则返回答案
}
};
4、复杂度分析
时间复杂度
- 图的构建：
O(E)，其中E是边的数量。 - Dijkstra 算法：
O((E + V) log V)，其中E是边数，V是节点数。使用优先队列实现 Dijkstra，时间复杂度为O((E + V) log V)。
因此，整体时间复杂度为 O((E + V) log V)。
空间复杂度
- 使用了
O(V + E)的空间来存储图和优先队列。
Q4、统计 K 次操作以内得到非递减子数组的数目
1、题目描述
给你一个长度为 n 的数组 nums 和一个整数 k 。
对于 nums 中的每一个子数组，你可以对它进行 至多 k 次操作。每次操作中，你可以将子数组中的任意一个元素增加 1 。
注意 ，每个子数组都是独立的，也就是说你对一个子数组的修改不会保留到另一个子数组中。
请你返回最多 k 次操作以内，有多少个子数组可以变成 非递减 的。
如果一个数组中的每一个元素都大于等于前一个元素（如果前一个元素存在），那么我们称这个数组是 非递减 的。
2、解题思路
我们需要通过合理的算法找到最多 k 次操作可以使得多少个子数组变为非递减的。对于每一个子数组，考虑以下步骤：
- 单调队列：
- 我们可以通过滑动窗口和单调队列来优化子数组的判断过程。
- 在滑动窗口中，每次考虑将窗口的某一段变成非递减的子数组。
- 修正次数计算：
- 对于每个子数组，我们计算需要多少次操作使得它变为非递减。具体来说，如果
nums[i] > nums[i+1]，我们需要进行nums[i] - nums[i+1]次操作才能使得nums[i]小于或等于nums[i+1]。
- 对于每个子数组，我们计算需要多少次操作使得它变为非递减。具体来说，如果
- 左边界和右边界的维护：
- 对于每个子数组，我们维护左右边界，确保在窗口内的操作次数不超过
k。 - 如果窗口内的操作次数超过
k，则我们调整窗口的左边界。
- 对于每个子数组，我们维护左右边界，确保在窗口内的操作次数不超过
- 栈和单调队列的配合：
- 使用栈来维护每个元素的左边界和右边界，栈的作用是帮助我们快速找到某个元素的最近的一个较小元素。
- 单调队列用于保持当前窗口内的元素的单调性，从而帮助我们高效地计算每个子数组的操作次数。
3、代码实现
class Solution {
public:
long long countNonDecreasingSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector<int> left(n), right(n);
vector<int> s = {-1}; // 栈, 初始化为 -1
// 构造 left 和 right 数组
for (int i = 0; i < n; ++i) {
while (s.size() > 1 && nums[i] >= nums[s.back()]) {
right[s.back()] = i; // 更新右边界
s.pop_back();
}
left[i] = s.back(); // 栈顶是左侧 > nums[i] 的最近元素
s.push_back(i);
}
for (int i : s) {
if (i != -1) {
// 栈中剩余元素的右边界为 n
right[i] = n;
}
}
// 记录每个 i 右侧有哪些位置的 left 是 i
vector<vector<int>> g(n);
for (int w = 0; w < n; ++w) {
if (left[w] >= 0) {
g[left[w]].push_back(w);
}
}
// 滑动窗口 + 单调队列
long long ret = 0;
// 当前窗口内的修正次数
int cnt = 0;
// 窗口的左边界
int l = 0;
// 单调队列, 维护窗口最大值的下标
deque<int> q;
for (int r = 0; r < n; ++r) {
int x = nums[r];
// 计算窗口内最大值与当前值的差距
if (!q.empty()) {
cnt += max(nums[q.front()] - x, 0);
}
// 单调队列入队, 维持单调性
while (!q.empty() && nums[q.back()] <= x) {
q.pop_back();
}
q.push_back(r);
// 调整窗口右边界, 直到满足修正次数的限制
while (cnt > k) {
int out = nums[l];
for (int w : g[l]) {
if (w > r) {
break;
}
cnt -= (out - nums[w]) * (min(right[w] - 1, r) - w + 1);
}
++l;
// 单调队列出队
if (!q.empty() && q.front() < l) {
q.pop_front();
}
}
// 计算窗口内的子数组个数
ret += r - l + 1;
}
return ret;
}
};
4、复杂度分析
栈的处理：栈的操作复杂度是 O(n)。
滑动窗口和单调队列：每次右边界 r 只会被访问一次，因此整体时间复杂度为 O(n)。
总时间复杂度：由于主要的操作是 O(n)，因此整体时间复杂度为 O(n)。