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

閱讀時間約 4 分鐘


題目摘要

給定一個整數陣列 `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,這是最大的利潤。


結論

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


相關連結



avatar-img
2會員
8內容數
"TypeScript LeetCode" 以 TypeScript 為工具,深入解析 LeetCode 上的算法和資料結構問題,提供清晰解釋和程式碼示範,幫助您精進 TypeScript 技能,解決挑戰性問題,無論您的程式開發水平如何。讓我們一同鑽研、提升,迎接算法挑戰,成長技術專長!,快速提高您的技能水平
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
毛怪的沙龍 的其他內容
題目摘要 給定一個陣列 prices,其中 prices[i] 代表第 i 天的股票價格。你希望透過在某一天購買一股股票,並在未來的某一天賣出它,以最大化你的利潤。如果無法獲得任何利潤,則返回 0。
題目摘要: 在這篇文章中,我們將討論如何使用摩爾投票算法找出一個陣列中的「主要元素」。主要元素指的是在陣列中出現次數超過一半的元素,並且我們可以確定它一定存在於陣列中。這個算法的核心思想和應用將在本文中被詳細介紹。 題目知識點: 主要元素的定義和重要性。 摩爾投票算法的工作原理和優點。 先備知識
重要知識點: 1. TypeScript 全局擴展,使所有陣列都能使用 groupBy 方法。 2. 利用泛型創建彈性函數,提高代碼可重用性。 3. 迭代陣列中的元素,實現遍歷和處理功能。 4. 物件的鍵值對操作,用於建立以函數輸出為鍵的物件。
這篇文章介紹了如何建立一個時間限制的異步函數,以確保操作在指定時間內完成。 - 知識點包括異步編程、Promise使用、計時器函數和函數引數處理,以及錯誤處理。 - 應用情境包括網頁請求超時控制、前端性能優化和遊戲開發。 - 提高應用程式的可靠性和用戶體驗,確保操作不會花費過長的時間。 - 文章內
[Leetcode 筆記] TypeScript 2715. Timeout Cancellation 了解和有效使用 clearTimeout 和 setTimeout 可以提高JavaScript程序的效率和響應性。
題目摘要 給定一個陣列 prices,其中 prices[i] 代表第 i 天的股票價格。你希望透過在某一天購買一股股票,並在未來的某一天賣出它,以最大化你的利潤。如果無法獲得任何利潤,則返回 0。
題目摘要: 在這篇文章中,我們將討論如何使用摩爾投票算法找出一個陣列中的「主要元素」。主要元素指的是在陣列中出現次數超過一半的元素,並且我們可以確定它一定存在於陣列中。這個算法的核心思想和應用將在本文中被詳細介紹。 題目知識點: 主要元素的定義和重要性。 摩爾投票算法的工作原理和優點。 先備知識
重要知識點: 1. TypeScript 全局擴展,使所有陣列都能使用 groupBy 方法。 2. 利用泛型創建彈性函數,提高代碼可重用性。 3. 迭代陣列中的元素,實現遍歷和處理功能。 4. 物件的鍵值對操作,用於建立以函數輸出為鍵的物件。
這篇文章介紹了如何建立一個時間限制的異步函數,以確保操作在指定時間內完成。 - 知識點包括異步編程、Promise使用、計時器函數和函數引數處理,以及錯誤處理。 - 應用情境包括網頁請求超時控制、前端性能優化和遊戲開發。 - 提高應用程式的可靠性和用戶體驗,確保操作不會花費過長的時間。 - 文章內
[Leetcode 筆記] TypeScript 2715. Timeout Cancellation 了解和有效使用 clearTimeout 和 setTimeout 可以提高JavaScript程序的效率和響應性。
你可能也想看
Google News 追蹤
Thumbnail
國泰CUBE App 整合外幣換匯、基金、證券等服務,提供簡便、低成本的美股定期定額投資解決方案。 5分鐘開戶、低投資門檻,幫助新手輕鬆進軍國際股市;提供人氣排行榜,讓投資人能夠掌握市場趨勢。
Thumbnail
TSM 公布 3Q24 財報,營收報 235.0 億美元,約合於我們 model 預期的 234.7 億美元,以及 Bloomberg 共識預期的 234.5 億美元,而本次財報最令人驚訝的是毛利率大幅提升至 57.8%,超越我們和 Bloomberg 預期的 55.0%,也大幅超越財測區間 53.
Thumbnail
題目摘要 給定一個陣列 prices,其中 prices[i] 代表第 i 天的股票價格。你希望透過在某一天購買一股股票,並在未來的某一天賣出它,以最大化你的利潤。如果無法獲得任何利潤,則返回 0。
Thumbnail
隨著科技的進步和遠程工作的興起,通訊方式正在經歷劇變。然而,這也讓許多人對於傳統的電話禮儀感到困惑。美國禮儀專家Lizzie Post針對這一問題,提出了六大電話禮儀建議,幫助我們在新的通訊環境下保持專業和禮貌。
Thumbnail
上週的雙11大家有買東西嗎? 去年雙11購入了tokuto的眼部按摩器TS-183使用滿一年心得分享給大家,希望能幫助跟我一樣眼睛容易酸澀又找不到相關心得文的人~
2021年底前價格應該會在 112-120之間移動
Thumbnail
電動汽車龍頭 Tesla,正式發布了他們在今年第二季的財報,交出了非常亮眼的成績,無論是在營收,或者是獲利上,都超過了市場上的分析師預期,也讓盤後特斯拉的股價上漲了 1%。當然,作為市場上最熱門的股票之一,特斯拉的營運狀況是非常多人關注的焦點,所以就讓科技巨頭解碼來帶大家看特斯拉最新一季的財報重點。
Thumbnail
國泰CUBE App 整合外幣換匯、基金、證券等服務,提供簡便、低成本的美股定期定額投資解決方案。 5分鐘開戶、低投資門檻,幫助新手輕鬆進軍國際股市;提供人氣排行榜,讓投資人能夠掌握市場趨勢。
Thumbnail
TSM 公布 3Q24 財報,營收報 235.0 億美元,約合於我們 model 預期的 234.7 億美元,以及 Bloomberg 共識預期的 234.5 億美元,而本次財報最令人驚訝的是毛利率大幅提升至 57.8%,超越我們和 Bloomberg 預期的 55.0%,也大幅超越財測區間 53.
Thumbnail
題目摘要 給定一個陣列 prices,其中 prices[i] 代表第 i 天的股票價格。你希望透過在某一天購買一股股票,並在未來的某一天賣出它,以最大化你的利潤。如果無法獲得任何利潤,則返回 0。
Thumbnail
隨著科技的進步和遠程工作的興起,通訊方式正在經歷劇變。然而,這也讓許多人對於傳統的電話禮儀感到困惑。美國禮儀專家Lizzie Post針對這一問題,提出了六大電話禮儀建議,幫助我們在新的通訊環境下保持專業和禮貌。
Thumbnail
上週的雙11大家有買東西嗎? 去年雙11購入了tokuto的眼部按摩器TS-183使用滿一年心得分享給大家,希望能幫助跟我一樣眼睛容易酸澀又找不到相關心得文的人~
2021年底前價格應該會在 112-120之間移動
Thumbnail
電動汽車龍頭 Tesla,正式發布了他們在今年第二季的財報,交出了非常亮眼的成績,無論是在營收,或者是獲利上,都超過了市場上的分析師預期,也讓盤後特斯拉的股價上漲了 1%。當然,作為市場上最熱門的股票之一,特斯拉的營運狀況是非常多人關注的焦點,所以就讓科技巨頭解碼來帶大家看特斯拉最新一季的財報重點。