每日算法 - 2025年4月30日

記錄下今天解決的兩道題目。

---

870. 優勢洗牌 (Advantage Shuffle)

題目描述

解題思路與方法

核心思想：貪心策略 (田忌賽馬)

這道題的目標是對于 nums1 中的每個元素，找到 nums2 中一個比它小的元素進行配對（如果可能），使得優勢配對的數量最大化。如果 nums1 中的某個元素找不到 nums2 中可以戰勝的對手，那么就用它去對付 nums2 中最強的對手，以保存 nums1 中更強的元素去對付 nums2 中可以戰勝的對手。這類似于經典的“田忌賽馬”策略。

具體步驟：

1. 排序 nums1：將 nums1 升序排序，這樣我們可以從小到大處理 nums1 中的元素。
2. 排序 nums2 的索引：我們不能直接排序 nums2，因為需要保留其原始元素的下標信息以構建最終結果 ret。因此，我們創建一個索引數組 indexs，存儲 0 到 n-1。然后根據 nums2 中對應索引位置的元素值對 indexs 進行升序排序。排序后，indexs[0] 指向 nums2 中最小元素的原始索引，indexs[n-1] 指向 nums2 中最大元素的原始索引。
3. 雙指針分配：
   • 使用兩個指針 left 和 right 分別指向 indexs 數組的開始（對應 nums2 最小值）和結束（對應 nums2 最大值）。
   • 使用一個指針 i 遍歷排序后的 nums1 (從 i=0 開始)。
   • 比較 nums1[i] (當前 nums1 中最小的可用元素) 和 nums2[indexs[left]] (當前 nums2 中最小的未匹配元素)。
   • 如果 nums1[i] > nums2[indexs[left]]：說明 nums1[i] 可以戰勝 nums2 中當前最小的對手。這是一個優勢匹配。我們將 nums1[i] 分配給 nums2 中這個最小對手的原始位置，即 ret[indexs[left]] = nums1[i]。然后移動 left 指針 (left++)，考慮 nums2 中下一個最小的對手。
   • 如果 nums1[i] <= nums2[indexs[left]]：說明 nums1[i] 連 nums2 中當前最小的對手都無法戰勝。根據貪心策略，這個 nums1[i] 應該去對付 nums2 中最強的對手（反正也打不過，不如消耗掉對方最強的），以保留 nums1 中更強的元素。我們將 nums1[i] 分配給 nums2 中當前最大對手的原始位置，即 ret[indexs[right]] = nums1[i]。然后移動 right 指針 (right--)，考慮 nums2 中下一個最大的對手。
   • 無論哪種情況，nums1[i] 都已經被使用，所以移動 i 指針 (i++) 處理 nums1 中的下一個元素。
4. 循環繼續：重復步驟 3，直到 left > right，此時所有 nums1 中的元素都已分配完畢。
5. 返回結果數組 ret。

復雜度分析

• 時間復雜度: $O(N\log N)$。主要是排序 nums1 和 indexs 數組所需的時間。雙指針遍歷過程是 $O(N)$ 的。
• 空間復雜度: $O(N)$。需要額外的空間存儲 indexs 數組和結果數組 ret。

Code

class Solution {public int[] advantageCount(int[] nums1, int[] nums2) {int n = nums2.length;Integer[] indexs = new Integer[n];for (int i = 0; i < n; i++) {indexs[i] = i;}Arrays.sort(nums1);Arrays.sort(indexs, (a, b) -> (nums2[a] - nums2[b]));int left = 0, right = n - 1;int i = 0;int[] ret = new int[n];while (left <= right) {int index = 0;if (nums1[i] <= nums2[indexs[left]]) {index = indexs[right];right--;} else {index = indexs[left];left++;}ret[index] = nums1[i];i++;}return ret;}
}

---

3402. 使每一列嚴格遞增的最少操作次數 (Minimum Operations to Make Columns Strictly Increasing)

題目描述

解題思路與方法

核心思想：貪心策略

題目要求我們用最少的操作次數使得網格 grid 的每一列都嚴格遞增。對于每一列，我們需要確保 grid[j][i] > grid[j-1][i] 對所有 j > 0 成立。

為了使操作次數最少，當發現 grid[j][i] <= grid[j-1][i] 時，我們應該將 grid[j][i] 增加到剛好滿足嚴格遞增條件的最小值，即 grid[j-1][i] + 1。

具體步驟：

1. 初始化總操作次數 ret = 0。
2. 遍歷每一列：外層循環遍歷列索引 i 從 0 到 grid[0].length - 1。
3. 遍歷每一行的元素（從第二行開始）：內層循環遍歷行索引 j 從 1 到 grid.length - 1。
4. 檢查條件：在每一列內部，比較當前元素 grid[j][i] 和它正上方的元素 grid[j-1][i]。
5. 執行操作：
   • 如果 grid[j][i] <= grid[j-1][i]，說明不滿足嚴格遞增條件。
   • 計算需要增加的值：increase = (grid[j-1][i] + 1) - grid[j][i]。
   • 將這個增加的值累加到總操作次數 ret 中。
   • 關鍵：更新 grid[j][i] 的值 為 grid[j-1][i] + 1。這一步非常重要，因為下一行的元素 grid[j+1][i] 需要和 更新后 的 grid[j][i] 進行比較。
6. 遍歷完所有列和行后，ret 就是所需的最小總操作次數。
7. 返回 ret。

復雜度分析

• 時間復雜度: $O(R\times C)$，其中 R 是網格的行數，C 是網格的列數。我們需要遍歷網格中的每個元素一次（除了第一行）。
• 空間復雜度: $O(1)$。我們是在原地修改 grid（雖然題目可能沒要求必須原地修改，但這樣做不影響結果且節省空間），只需要常數級別的額外空間存儲變量 ret、i、j 等。

Code

class Solution {public int minimumOperations(int[][] grid) {int ret = 0;for (int i = 0; i < grid[0].length; i++) {for (int j = 1; j < grid.length; j++) {if (grid[j][i] <= grid[j - 1][i]) {ret += (grid[j - 1][i] + 1 - grid[j][i]);grid[j][i] = grid[j - 1][i] + 1;}}}return ret;}
}

---