[TS LeetCode] 122. Best Time to Buy and Sell Stock II+貪婪演算法

題目摘要

給定一個整數陣列 `prices`，其中 `prices[i]` 代表第 `i` 天的股票價格。在每一天，你可以決定買入和/或賣出股票。然而，你同一時間只能擁有至多一股股票。你可以在同一天內買入然後立刻賣出股票。找出並返回你可以實現的最大利潤。

貪婪演算法(Greedy algorithm)：

• 貪婪演算法通常用於優化問題，其中需要在一組可能的選擇中選擇最佳解決方案，以最大化或最小化某個目標函數。
• 貪婪演算法基於當前情況下的最佳選擇，而不關心全局的最優解。
• 在每一步，貪婪演算法都選擇當前情況下的最佳選擇，並且不會回頭更改之前的選擇。

特色：

1. 局部最佳選擇：貪婪演算法選擇的是局部最佳選擇，即在每一步都儘量達到最有利的結果，而不考慮全局最優解。這使得貪婪演算法容易實現和理解。
2. 無回頭修改：一旦貪婪演算法做出了選擇，就不會回頭更改。這意味著它不考慮之前的決策對未來決策的影響，因此通常不需要記錄整個決策過程的歷史。
3. 適用性：貪婪演算法適用於具有最佳子結構性質和無後效性的問題。最佳子結構性質表示全局最優解可以由局部最佳解組合而成，而無後效性表示過去的決策不會影響未來的決策。
4. 效率：貪婪演算法通常具有較低的計算成本和更快的執行速度，因為它僅關注當前情況。
5. 不保證最優解：貪婪演算法不保證找到全局最優解，因為它忽略了全局的考慮。它可能會找到一個接近最優解的解，但不一定是最佳的。

總而言之，貪婪演算法是一種簡單而有效的問題解決方法，特別適用於某些問題，其中局部最佳選擇能夠導致全局最優解。然而，它不適用於所有問題，且無法保證最優解，因此在應用時需要謹慎考慮問題的特性和要求。

解題思路

1. 問題理解：首先，仔細閱讀題目，了解它要求我們根據每天的股票價格，找出最佳的交易策略，以最大化利潤。關鍵是我們可以在同一天內買入和賣出，並且可以多次進行交易。
2. 貪婪策略：明確了解貪婪策略的應用，即在每一天只要價格上升，就執行交易，以實現價格增長的利潤。我們不需要等到價格達到最高點才賣出。
3. 演算法實現：遍歷股票價格陣列，檢查相鄰兩天的價格。如果今天的價格高於昨天，我們執行買入和賣出操作，並將利潤累積到最終的最大利潤中。
4. 程式碼實現：將這個貪婪策略轉化為程式碼。使用一個迴圈來遍歷價格陣列，並使用條件語句檢查價格的變化。如果價格上升，就進行交易操作，並更新最大利潤。

function maxProfit(prices: number[]): number {
    let maxProfit: number = 0;

    for (let i = 1; i < prices.length; i++) {
        if (prices[i - 1] < prices[i]) {
            maxProfit += prices[i] - prices[i - 1];
        }
    }
    return maxProfit;
};

貪婪演算法的應用

在這個問題中，貪婪策略是基於當前價格是否上升，來選擇買入和賣出操作，以實現利潤最大化。如果當前一天的股價高於前一天，則可以考慮在前一天購入並當天賣出以獲得利潤。這是因為你可以在同一天內買入然後立刻賣出，並從價格上升中獲得利潤。如果價格下降或保持不變，則不執行交易操作，因為這樣可能不會增加利潤。

範例

假設股價變化如下： [7, 1, 5, 3, 6, 4]，根據貪婪策略，可以執行以下操作：

• 在第 2 天（價格 1）買入，第 3 天（價格 5）賣出，獲得利潤 4。
• 在第 4 天（價格 3）買入，第 5 天（價格 6）賣出，獲得利潤 3。

總利潤為 4 + 3 = 7，這是最大的利潤。

結論

因此，在這個問題中，貪婪演算法的應用是通過根據當前價格的變化來執行交易操作，而不需要預測未來價格變化趨勢，以實現最大化的利潤。這個方法在簡單且有效的情況下非常適用，並且在實務應用中具有廣泛的用途。

相關連結