第432场周赛：跳过交替单元格的之字形遍历、机器人可以获得的最大金币数、图的最大边权的最小值、统计 K 次操作以内得到非递减子数组的数目

Q1、跳过交替单元格的之字形遍历

1、题目描述

给你一个 m x n 的二维数组 grid，数组由 正整数 组成。

你的任务是以 之字形 遍历 grid，同时跳过每个 交替 的单元格。

之字形遍历的定义如下：

• 从左上角的单元格 (0, 0) 开始。
• 在当前行中向 右 移动，直到到达该行的末尾。
• 下移到下一行，然后在该行中向 左 移动，直到到达该行的开头。
• 继续在行间交替向右和向左移动，直到所有行都被遍历完。

**注意：**在遍历过程中，必须跳过每个 交替 的单元格。

返回一个整数数组 result，其中包含按 顺序 记录的、且跳过交替单元格后的之字形遍历中访问到的单元格值。

2、解题思路

1. 方向交替：

   • 遍历过程中，偶数行从左到右，奇数行从右到左。可以使用 reverse 方法在遍历奇数行时反转数组。

2. 跳过单元格：

   • 通过布尔变量 flag 来控制是否访问当前单元格。

   • 每访问一个单元格后，将 flag 取反，跳过下一个单元格。

3. 结果记录：

   • 将每次访问到的单元格值存入结果数组 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、复杂度分析

时间复杂度分析

1. 行遍历：
   • 外层 for 循环遍历所有 m 行。
2. 行内遍历：
   • 每行遍历 n 个元素，共访问 $m\times n$ 个单元格。
   • 奇数行反转操作的复杂度为 O(n)。

总时间复杂度： $O(m\times n)$

空间复杂度分析

1. 额外空间：
   • 结果数组 ret 存储跳过单元格后的值，大小最多为 $\lceil m\times n/2\rceil$。
   • 反转操作在原地完成，不需要额外空间。

总空间复杂度： $O(m\times 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 个强盗后能够获得的最大金币数。

动态规划转移方程

1. 定义状态

   • dp[i][j][k]：到达单元 (i, j)，感化了 k 个强盗后的最大金币数。
   • k 的范围为 [0, 2]，表示机器人最多能感化 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) ：
       • 与从上方的情况类似。

3. 初始条件

   • 对于起点 (0, 0) ：
     • 如果 coins[0][0] >= 0，金币数为 coins[0][0]。
     • 如果 coins[0][0] < 0 且感化强盗次数 k > 0，金币数为 0（感化该强盗）。

4. 最终结果

   • 机器人到达右下角 (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) {// 遍历感化强盗的次数 kfor (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\times n\times 3)=O(m\times n)$。

空间复杂度

• 使用了一个三维数组 dp，大小为 $O(m\times n\times 3)$。

Q3、图的最大边权的最小值

1、题目描述

给你两个整数 n 和 threshold ，同时给你一个 n 个节点的 有向 带权图，节点编号为 0 到 n - 1 。这个图用 二维 整数数组 edges 表示，其中 edges[i] = [Ai, Bi, Wi] 表示节点 Ai 到节点 Bi 之间有一条边权为 Wi的有向边。

你需要从这个图中删除一些边（也可能 不 删除任何边），使得这个图满足以下条件：

• 所有其他节点都可以到达节点 0 。
• 图中剩余边的 最大 边权值尽可能小。
• 每个节点都 至多 有 threshold 条出去的边。

请你返回删除必要的边后，最大 边权的 最小值 为多少。如果无法满足所有的条件，请你返回 -1

2、解题思路

本题本质上是一个 图的最短路径问题，但有多个限制条件。我们可以通过以下步骤来思考并解决问题：

1. 反向图构建
   我们需要从每个节点到达节点 0，所以我们构建图的 反向图。反向图中，原本从 Ai 到 Bi 的边变为从 Bi 到 Ai 的边。这样，我们只需要考虑从节点 0 到其他节点的路径即可。

2. 最大边权最小化
   为了确保所有的节点都能到达节点 0，且最大边权最小，我们需要使用 最短路径算法。这里的最短路径的定义是：我们要求路径中的 最大边权最小，这和普通的最短路径问题有些不同。

   我们可以使用 Dijkstra 算法 来解决这个问题。Dijkstra 算法通常用于找到从起点到所有其他节点的最短路径，而在这个问题中，我们可以将路径的 “最短” 定义为 “最大边权最小”。

3. 满足 threshold 条件
   限制每个节点至多有 threshold 条出去的边，意味着我们需要在考虑边的同时，保持每个节点的出度不超过 threshold。这个限制可以通过构建图时进行检查。

4. 最终返回
   经过 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 的边权为 wfor (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 次操作可以使得多少个子数组变为非递减的。对于每一个子数组，考虑以下步骤：

1. 单调队列：
   • 我们可以通过滑动窗口和单调队列来优化子数组的判断过程。
   • 在滑动窗口中，每次考虑将窗口的某一段变成非递减的子数组。
2. 修正次数计算：
   • 对于每个子数组，我们计算需要多少次操作使得它变为非递减。具体来说，如果 nums[i] > nums[i+1]，我们需要进行 nums[i] - nums[i+1] 次操作才能使得 nums[i] 小于或等于 nums[i+1]。
3. 左边界和右边界的维护：
   • 对于每个子数组，我们维护左右边界，确保在窗口内的操作次数不超过 k。
   • 如果窗口内的操作次数超过 k，则我们调整窗口的左边界。
4. 栈和单调队列的配合：
   • 使用栈来维护每个元素的左边界和右边界，栈的作用是帮助我们快速找到某个元素的最近的一个较小元素。
   • 单调队列用于保持当前窗口内的元素的单调性，从而帮助我们高效地计算每个子数组的操作次数。

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) {// 栈中剩余元素的右边界为 nright[i] = n;}}// 记录每个 i 右侧有哪些位置的 left 是 ivector<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)。