貪心算法精解（Java實現）：從理論到實戰

一、貪心算法概述

貪心算法（Greedy Algorithm）是一種在每一步選擇中都采取當前狀態下最優決策的算法策略。它通過局部最優選擇來達到全局最優解，具有高效、簡潔的特點。

核心特點：

局部最優選擇：每一步都做出當前看來最佳的選擇，即在當前狀態下，不考慮整體的最優解，只關注眼前的最優決策。
無后效性：當前決策不會影響后續決策，也就是說，在做出當前的最優選擇后，不會改變未來狀態的決策空間和決策方式。
高效性：通常時間復雜度較低，相比于一些需要窮舉所有可能性的算法，貪心算法能更快地得到結果。

適用場景：

問題具有最優子結構：即問題的最優解包含了其子問題的最優解。例如，在區間調度問題中，全局的最優區間選擇方案包含了每個子區間的最優選擇。
問題具有貪心選擇性質：通過一系列局部最優選擇可以得到全局最優解。這是貪心算法能夠應用的關鍵條件。
不需要回溯或考慮所有可能性：貪心算法在每一步都直接做出選擇，而不需要回頭修改之前的決策，也不需要考慮所有可能的情況。

二、貪心算法基本框架（Java 實現）

import java.util.List;// 假設Problem類是存儲問題相關數據的類
class Problem {private List<Item> items;public Problem(List<Item> items) {this.items = items;}public List<Item> getItems() {return items;}
}// 假設Item類是表示問題中每個元素的類
class Item {// 可以根據具體問題添加屬性和方法
}// 假設Solution類是存儲最終解決方案的類
class Solution {// 可以根據具體問題添加屬性和方法，用于存儲和操作解決方案public void add(Item item) {// 實現將item添加到解決方案中的邏輯}
}public class GreedyAlgorithm {public static Solution greedySolution(Problem problem) {// 1. 初始化解決方案Solution solution = new Solution();// 2. 對輸入進行預處理（如排序）List<Item> items = preprocess(problem.getItems());// 3. 貪心選擇過程for (Item item : items) {if (canSelect(item, solution)) {solution.add(item);}}// 4. 返回最終解return solution;}private static List<Item> preprocess(List<Item> items) {// 根據具體問題實現對輸入數據的預處理，例如排序// 這里簡單返回原數據，實際應用中需要進行處理return items;}private static boolean canSelect(Item item, Solution solution) {// 判斷當前項是否能被選中// 根據具體問題實現return true;}
}

三、經典貪心算法問題

3.1 找零錢問題（Coin Change）

import java.util.Arrays;public class CoinChange {public static int minCoins(int[] coins, int amount) {Arrays.sort(coins); // 先排序，將硬幣面額從小到大排列int count = 0;int index = coins.length - 1; // 從最大面額開始，因為要盡可能使用大面額的硬幣以減少硬幣數量while (amount > 0 && index >= 0) {if (coins[index] <= amount) {int num = amount / coins[index]; // 計算當前面額硬幣的使用數量count += num; // 將使用數量累加到總硬幣數中amount -= num * coins[index]; // 從總金額中減去已使用的硬幣金額}index--; // 嘗試下一個較小面額的硬幣}return amount == 0? count : -1; // 如果金額正好用完，返回總硬幣數；否則返回-1表示無法找零}
}

3.2 區間調度問題（Interval Scheduling）

import java.util.Arrays;public class IntervalScheduling {public static int maxNonOverlappingIntervals(int[][] intervals) {if (intervals == null || intervals.length == 0) return 0;// 按照結束時間排序，這樣能保證每次選擇的區間結束時間最早，為后續選擇留出更多空間Arrays.sort(intervals, (a, b) -> a[1] - b[1]);int count = 1; // 至少有一個區間可以選擇int end = intervals[0][1]; // 記錄當前已選區間的結束時間for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] >= end) {count++; // 找到一個不重疊的區間，區間數量加1end = intervals[i][1]; // 更新當前已選區間的結束時間}}return count;}
}

四、LeetCode 經典題目解析

4.1 買賣股票的最佳時機 II（LeetCode 122）

class Solution {public int maxProfit(int[] prices) {int profit = 0;for (int i = 1; i < prices.length; i++) {if (prices[i] > prices[i - 1]) {profit += prices[i] - prices[i - 1]; // 如果今天的價格比昨天高，就進行買賣獲取利潤}}return profit;}
}

這道題的貪心策略是：只要今天的股票價格比昨天高，就進行一次買賣操作，獲取差價利潤。因為可以進行多次買賣，所以每次價格上漲都能帶來利潤，最終得到的總利潤就是最大利潤。

4.2 跳躍游戲（LeetCode 55）

class Solution {public boolean canJump(int[] nums) {int maxReach = 0;for (int i = 0; i < nums.length; i++) {if (i > maxReach) return false; // 如果當前位置超過了能到達的最大位置，說明無法到達終點maxReach = Math.max(maxReach, i + nums[i]); // 更新能到達的最大位置if (maxReach >= nums.length - 1) return true; // 如果能到達的最大位置已經超過或等于終點，說明可以到達終點}return true;}
}

這道題的貪心策略是：在遍歷數組的過程中，不斷更新能到達的最大位置。如果當前位置超過了能到達的最大位置，說明無法繼續前進；如果能到達的最大位置已經超過或等于終點，說明可以到達終點。

五、貪心算法解題技巧

排序預處理：大多數貪心問題需要先對輸入數據進行排序
- 按開始時間、結束時間、權重等關鍵屬性排序。例如在區間調度問題中，按照區間的結束時間排序，能保證每次選擇的區間結束時間最早，為后續選擇留出更多空間。
優先隊列應用：處理需要動態獲取最優解的問題
```
PriorityQueue<Integer> pq = new PriorityQueue<>();
```

優先隊列可以在每次操作中快速獲取當前的最優元素，適用于需要動態維護最優解的場景，比如在一些涉及到權重或優先級的問題中。
3.?雙指針技巧：適用于區間類問題

int left = 0, right = array.length - 1;

雙指針可以在數組或區間上進行高效的遍歷和操作，通過兩個指針的移動來解決一些與區間相關的問題，比如尋找最長不重疊區間等。
4.?貪心選擇證明：

交換論證法：通過交換當前貪心選擇和其他選擇，證明貪心選擇不會導致更差的結果。
數學歸納法：證明對于小規模問題貪心選擇是正確的，然后假設對于規模為 n 的問題貪心選擇正確，證明對于規模為 n+1 的問題貪心選擇也正確。
反證法：假設貪心選擇不是最優的，推出矛盾，從而證明貪心選擇是最優的。

六、貪心算法的局限性

不能保證全局最優：某些問題無法通過貪心算法得到最優解。因為貪心算法只考慮當前的最優選擇，而沒有考慮整體的情況，可能會陷入局部最優解。
適用范圍有限：僅適用于具有貪心選擇性質的問題。如果問題不滿足貪心選擇性質，使用貪心算法可能得到錯誤的結果。
需要嚴格證明：必須證明貪心選擇的正確性。在應用貪心算法之前，需要通過數學證明或其他方法來驗證貪心策略的有效性，否則可能無法得到正確的結果。

七、實戰建議

識別貪心性質：分析問題是否具有貪心選擇性質。可以通過嘗試一些簡單的例子，觀察是否可以通過局部最優選擇得到全局最優解。
從簡單案例入手：通過小例子驗證貪心策略。在解決復雜問題之前，先從簡單的情況開始，驗證貪心策略的正確性和有效性。
與動態規劃對比：當貪心不適用時考慮動態規劃。如果發現問題不滿足貪心選擇性質，或者貪心算法無法得到最優解，可以考慮使用動態規劃等其他算法。
邊界條件檢查：特別注意空輸入、極值等情況。在編寫代碼時，要考慮到各種可能的邊界情況，避免出現錯誤。

八、進階練習

分發餅干（LeetCode 455）
無重疊區間（LeetCode 435）
加油站問題（LeetCode 134）
任務調度器（LeetCode 621）

// 示例：分發餅干（LeetCode 455）
import java.util.Arrays;class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g); // 對孩子的胃口大小進行排序Arrays.sort(s); // 對餅干的大小進行排序int i = 0, j = 0;while (i < g.length && j < s.length) {if (s[j] >= g[i]) {i++; // 如果當前餅干能滿足當前孩子的胃口，孩子數量加1}j++; // 無論是否能滿足，都嘗試下一塊餅干}return i; // 返回能滿足的孩子數量}
}