第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\times n$ 個單元格。
- 奇數行反轉操作的復雜度為 O(n)。

總時間復雜度： $\times n)$

空間復雜度分析

額外空間：
- 結果數組 ret 存儲跳過單元格后的值，大小最多為 $\lceil m \times n / 2 \rceil$ 。
- 反轉操作在原地完成，不需要額外空間。

總空間復雜度： $\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 個強盜后能夠獲得的最大金幣數。

動態規劃轉移方程

定義狀態
- 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) {// 遍歷感化強盜的次數 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，總復雜度為 $\times n \times 3) = O(m \times n)$ 。

空間復雜度

使用了一個三維數組 dp，大小為 $\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、解題思路

本題本質上是一個 圖的最短路徑問題，但有多個限制條件。我們可以通過以下步驟來思考并解決問題：

反向圖構建
我們需要從每個節點到達節點 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 的邊權為 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 次操作可以使得多少個子數組變為非遞減的。對于每一個子數組，考慮以下步驟：

單調隊列：
- 我們可以通過滑動窗口和單調隊列來優化子數組的判斷過程。
- 在滑動窗口中，每次考慮將窗口的某一段變成非遞減的子數組。
修正次數計算：
- 對于每個子數組，我們計算需要多少次操作使得它變為非遞減。具體來說，如果 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) {// 棧中剩余元素的右邊界為 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;}
};

在這里插入圖片描述