貪心算法經典題目總結（C++實現）

貪心算法是一種在每一步選擇中都采取當前狀態下最優（即最有利）的選擇，從而希望導致結果是全局最優的算法。本文總結了四道經典的貪心算法問題，幫助你更好地理解和掌握貪心算法的應用。

---

🟢 1. 買賣股票的最佳時機（Best Time to Buy and Sell Stock）

📄 題目描述：

給定一個數組 prices，其中第 i 個元素是第 i 天的股票價格。假設你最多只能進行一次交易（即買入和賣出一支股票），設計一個算法來計算你所能獲取的最大利潤。

🧠 解題思路（簡潔版）

• 一次遍歷：
  • 遍歷價格數組，維護當前最低價格 minp 和最大利潤 maxp。
  • 每天更新最低價格和最大利潤。

?? 復雜度分析

• 時間復雜度：O(n)，其中 n 為價格數組長度。
• 空間復雜度：O(1)。

? C++ 實現

class Solution {
public:int maxProfit(vector<int>& prices) {int minp = 1e9, maxp = 0;for (auto& price : prices) {maxp = max(maxp, price - minp);minp = min(minp, price);}return maxp;}
};

---

🟢 2. 跳躍游戲（Jump Game）

📄 題目描述：

給定一個非負整數數組 nums，你最初位于數組的第一個位置。數組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最后一個位置。

🧠 解題思路（簡潔版）

• 貪心算法：
  • 遍歷數組，維護當前能到達的最遠位置 rightmost。
  • 若當前位置可達，則更新最遠位置。
  • 若最遠位置覆蓋數組末尾，返回 true。

?? 復雜度分析

• 時間復雜度：O(n)，其中 n 為數組長度。
• 空間復雜度：O(1)。

? C++ 實現

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();int rightmost = 0;for (int i = 0; i < n; i++) {if (i <= rightmost) {rightmost = max(rightmost, i + nums[i]);if (rightmost >= n - 1) return true;}}return false;}
};

---

🟢 3. 跳躍游戲 II（Jump Game II）

📄 題目描述：

給定一個非負整數數組 nums，你最初位于數組的第一個位置。數組中的每個元素代表你在該位置可以跳躍的最大長度。你的目標是使用最少的跳躍次數到達數組的最后一個位置。

🧠 解題思路（簡潔版）

• 貪心算法：
  • 遍歷數組，維護當前能到達的最遠位置 maxpos 和當前步的邊界 end。
  • 若當前位置到達邊界，則更新邊界為最遠位置并增加步數。
  • 直到覆蓋數組末尾。

?? 復雜度分析

• 時間復雜度：O(n)，其中 n 為數組長度。
• 空間復雜度：O(1)。

? C++ 實現

class Solution {
public:int jump(vector<int>& nums) {int maxpos = 0, n = nums.size(), end = 0, step = 0;for (int i = 0; i < n - 1; i++) {if (maxpos >= i) {maxpos = max(maxpos, i + nums[i]);if (i == end) {end = maxpos;step++;}}}return step;}
};

---

🟢 4. 劃分字母區間（Partition Labels）

📄 題目描述：

給定一個字符串 s，將字符串劃分成若干個字母區間，每個區間內的字母互不相同。返回每個區間的長度。

🧠 解題思路（簡潔版）

• 貪心算法：
  • 預處理每個字符的最后出現位置。
  • 遍歷字符串，維護當前區間的起始和結束位置。
  • 當遍歷到當前區間的結束位置時，記錄區間長度并更新起始位置。

?? 復雜度分析

• 時間復雜度：O(n)，其中 n 為字符串長度。
• 空間復雜度：O(1)，固定大小的數組。

? C++ 實現

class Solution {
public:vector<int> partitionLabels(string s) {int last[26];int length = s.size();for (int i = 0; i < length; i++) {last[s[i] - 'a'] = i;}vector<int> partition;int start = 0, end = 0;for (int i = 0; i < length; i++) {end = max(end, last[s[i] - 'a']);if (i == end) {partition.push_back(end - start + 1);start = end + 1;}}return partition;}
};

---

📌 總結

題目	方法	時間復雜度	空間復雜度
買賣股票的最佳時機	一次遍歷	O(n)	O(1)
跳躍游戲	貪心算法	O(n)	O(1)
跳躍游戲 II	貪心算法	O(n)	O(1)
劃分字母區間	貪心算法	O(n)	O(1)

---

希望本文對你有所幫助！如果你還有其他問題，歡迎繼續提問。