0121. 買賣股票的最佳時機 · ttttt

# 0121. 買賣股票的最佳時機 ## 題目地址(121. 買賣股票的最佳時機) <https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/description/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設計一個算法來計算你所能獲取的最大利潤。注意：你不能在買入股票前賣出股票。示例 1: 輸入: [7,1,5,3,6,4] 輸出: 5 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。示例 2: 輸入: [7,6,4,3,1] 輸出: 0 解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。 ``` ``` ## 前置知識 - [數組](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - amazon - bloomberg - facebook - microsoft - uber ## 思路由于我們是想獲取到最大的利潤，我們的策略應該是低點買入，高點賣出。由于題目對于交易次數有限制，只能交易一次，因此問題的本質其實就是求波峰浪谷的差值的最大值。用圖表示的話就是這樣： ![](https://img.kancloud.cn/a4/98/a49859816a3e8d63b42de5a218b93cf7_700x434.jpg) ## 關鍵點解析 - 這類題只要你在心中（或者別的地方）畫出上面這種圖就很容易解決 ## 代碼語言支持：JS，C++，Java，Python JS Code: ``` <pre class="calibre18">``` /** * @param {number[]} prices * @return {number} */ var maxProfit = function (prices) { let min = prices[0]; let profit = 0; // 7 1 5 3 6 4 for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { profit = Math.max(profit, prices[i] - min); } else { min = Math.min(min, prices[i]); } } return profit; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` /** * 系統上C++的測試用例中的輸入有[]，因此需要加一個判斷 */ class Solution { public: int maxProfit(vector<int>& prices) { if (prices.empty()) return 0; auto min = prices[0]; auto profit = 0; for (auto i = 1; i < prices.size(); ++i) { if (prices[i] > prices[i -1]) { profit = max(profit, prices[i] - min); } else { min = std::min(min, prices[i]);; } } return profit; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` class Solution { public int maxProfit(int[] prices) { int minprice = Integer.MAX_VALUE; int maxprofit = 0; for (int price: prices) { maxprofit = Math.max(maxprofit, price - minprice); minprice = Math.min(price, minprice); } return maxprofit; } } ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def maxProfit(self, prices: 'List[int]') -> int: if not prices: return 0 min_price = float('inf') max_profit = 0 for price in prices: if price < min_price: min_price = price elif max_profit < price - min_price: max_profit = price - min_price return max_profit ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 相關題目 - [122.best-time-to-buy-and-sell-stock-ii](122.best-time-to-buy-and-sell-stock-ii.html) - [309.best-time-to-buy-and-sell-stock-with-cooldown](309.best-time-to-buy-and-sell-stock-with-cooldown.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)