每日算法 - 2024-05-13

記錄今天學習的算法題解。

---

2335. 裝滿杯子需要的最短總時長

題目

思路

貪心

這道題的關鍵在于每次操作盡可能多地減少杯子的數量。我們每次操作可以裝一杯或兩杯（不同類型）。為了最小化總時間，應該優先選擇裝兩杯不同類型的水。

解題過程

問題的最優解受到兩個因素的制約：

1. 數量最多的那杯水：假設數量最多的水需要 max_val 杯。由于每次操作最多只能裝一杯這種類型的水，所以我們至少需要 max_val 秒才能把這種水裝完。這是一個時間的下限。
2. 總水量：假設總水量為 total_sum = amount[0] + amount[1] + amount[2]。由于每次操作最多裝兩杯水，裝完 total_sum 杯水至少需要 ceil(total_sum / 2) 秒。這里的 ceil 表示向上取整，因為如果總數是奇數，最后一次操作只能裝一杯。在整數除法中，(total_sum + 1) / 2 可以實現向上取整的效果。這也是一個時間的下限。

最短的總時長必須同時滿足這兩個下限條件。因此，最終答案就是這兩個下限中的較大值：max(max_val, (total_sum + 1) / 2)。

可以證明，總是存在一種貪心策略（例如，每次都優先選擇數量最多的兩種水來裝）可以達到這個下限。

復雜度

• 時間復雜度: $O(1)$。只需要進行常數次的比較和算術運算。
• 空間復雜度: $O(1)$。只需要常數級別的額外空間存儲變量。

Code

class Solution {public int fillCups(int[] amount) {// 找到數量最多的杯子數int maxVal = 0;int totalSum = 0;for (int count : amount) {maxVal = Math.max(maxVal, count);totalSum += count;}int avgOps = (totalSum + 1) / 2; return Math.max(maxVal, avgOps);}
}

---

1753. 移除石子的最大得分

題目

思路

貪心

目標是最大化操作次數（每次操作得1分）。每次操作需要從兩堆不同的非空石子堆中各取一個。為了盡可能多地進行操作，我們應該避免讓某一堆石子過早地被單獨剩下。因此，貪心策略是每次都選擇當前石子數最多的兩堆進行操作。

解題過程

為了方便分析，我們先對三堆石子的數量 a, b, c 進行排序，假設排序后為 min_val <= mid_val <= max_val。

考慮貪心策略：每次都從最多的兩堆（max_val 和 mid_val）中取石子。

分析兩種情況：

1. max_val >= mid_val + min_val:
   在這種情況下，最大堆的石子數量大于等于另外兩堆之和。我們可以將 mid_val 堆和 min_val 堆的石子完全與 max_val 堆配對消耗完。

2. max_val < mid_val + min_val:
   在這種情況下，最大堆的石子數不足以單獨消耗掉另外兩堆。這意味著我們可以持續地從最大的兩堆中取石子，直到所有石子幾乎被取完（最多只會剩下一個石子）。
   總石子數為 S = max_val + mid_val + min_val。每次操作減少2個石子。我們可以進行的操作次數取決于總石子數 S。

   • 如果 S 是偶數，最多可以進行 S / 2 次操作，最后沒有石子剩下。
   • 如果 S 是奇數，最多可以進行 (S - 1) / 2 次操作，最后會剩下1個石子。
     這兩種情況合并起來就是 floor(S / 2) 次操作。在整數除法中，(max_val + mid_val + min_val) / 2 正好計算出 floor(S / 2)。
     因此，最大得分為 (max_val + mid_val + min_val) / 2。

綜合這兩種情況，即為題解。

復雜度

• 時間復雜度: $O(1)$。對三個數排序（或找到最大、最小、中間值）以及后續計算都是常數時間。
• 空間復雜度: $O(1)$。只需要常數級別的額外空間。

Code

class Solution {public int maximumScore(int a, int b, int c) {int max = Math.max(a, Math.max(b, c));int min = Math.min(a, Math.min(b, c));int mid = (a + b + c) - (max + min);if (max >= mid + min) {return mid + min;} else {return (max + mid + min) / 2;}}
}

---

2592. 最大化數組的偉大值（復習）

題目

這是第二次寫這道題了，典型的田忌賽馬問題，寫的還不錯，就不多說了，詳細題解可以參考之前的筆記：每日算法-250428

Code

class Solution {public int maximizeGreatness(int[] nums) {int ret = 0;Arrays.sort(nums);int left = 0, right = nums.length - 1, i = right;while (left <= right) {if (nums[i] >= nums[right]) {left++;} else {ret++;right--;}i--;}return ret;}
}

---