121. 买卖股票的最佳时机(Best Time to Buy and Sell Stock)E
英文题目
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
中文题目
给定一个数组,它的第 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。
暴力解法
找出给定两个数字之间的最大差值(即最大利润)
注意,以下例子会超时
时间复杂度:O(n^2),空间复杂度O(1)
# python: 超时 class Solution: def maxProfit(self, prices: List[int]) -> int: res = 0 # 遍历所有的买入价格,最后一天买入无用 for buy in range(len(prices)-1): # 遍历买入价格后一天的所有卖出价格 for sell in range(buy+1, len(prices)): res = max(res, prices[sell] - prices[buy]) return res
// c++: 超时 class Solution { public: int maxProfit(vector<int>& prices) { int res = 0; for (int buy = 0; buy < prices.size()-1; ++buy) { for (int sell = buy+1; sell < prices.size(); ++sell) { res = max(res, prices[sell] - prices[buy]); } } return res; } };
// java: 超时 class Solution { public int maxProfit(int[] prices) { int res = 0; for (int buy = 0; buy < prices.length - 1; ++buy) { for (int sell = buy+1; sell < prices.length; ++sell) { res = Math.max(res, prices[sell] - prices[buy]); } } return res; } }
// go: 超时 func maxProfit(prices []int) int { res := 0 for buy := 0; buy < len(prices) - 1; buy++ { for sell := buy+1; sell < len(prices); sell++ { res = maxInt(res, prices[sell]-prices[buy]) } } return res } func maxInt(a, b int) int { if a >= b { return a } else { return b } }
// javascript: 超时 /** * @param {number[]} prices * @return {number} */ var maxProfit = function(prices) { let res = 0; for (let buy = 0; buy < prices.length - 1; ++buy) { for (let sell = buy+1; sell < prices.length; ++sell) { res = Math.max(res, prices[sell] - prices[buy]); } } return res; };
一次遍历(贪心)
一次遍历中,记录历史最低点,在每一天都进行计算,我今天卖出能赚多少钱
时间复杂度O(n),空间复杂度O(1)
# python: 时间 228 ms, 击败 51.53%; 内存 25.9 MB, 击败 61.17% class Solution: def maxProfit(self, prices: List[int]) -> int: # 初始化时,假设第一天为历史最低点 minPrice, res = prices[0], 0 for i in range(1, len(prices)): res = max(res, prices[i] - minPrice) minPrice = min(minPrice, prices[i]) return res
// c++: 时间 108 ms, 击败 55.45%; 内存 91.1 MB, 击败 77.38% class Solution { public: int maxProfit(vector<int>& prices) { int minPrice = prices[0], res = 0; for (int i = 1; i < prices.size(); ++i) { res = max(res, prices[i] - minPrice); minPrice = min(minPrice, prices[i]); } return res; } };
// java: 时间 2 ms, 击败 43.37%; 内存 57.4 MB, 击败 75.6% class Solution { public int maxProfit(int[] prices) { int minPrice = prices[0], res = 0; for (int i = 1; i < prices.length; ++i) { res = Math.max(res, prices[i] - minPrice); minPrice = Math.min(minPrice, prices[i]); } return res; } }
// go: 时间 104 ms, 击败 89.46%; 内存 8.05 MB, 击败 32.31% func maxProfit(prices []int) int { minPrice, res := prices[0], 0 for i := 0; i < len(prices); i++ { res = maxInt(res, prices[i] - minPrice) minPrice = minInt(minPrice, prices[i]) } return res } func maxInt(a, b int) int { if a > b { return a } else { return b } } func minInt(a, b int) int { if a < b { return a } else { return b } }
// javascript: 时间 68 ms, 击败 97.71%; 内存 49.34 MB, 击败 75.73% /** * @param {number[]} prices * @return {number} */ var maxProfit = function(prices) { let minPrice = prices[0], res = 0; for (let i = 0; i < prices.length; ++i) { res = Math.max(res, prices[i] - minPrice); minPrice = Math.min(minPrice, prices[i]); } return res; };