[LeetCode] 121. Best Time to Buy and Sell Stock
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 <= 105
0 <= prices[i] <= 104
买卖股票的最佳时机。
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题意是给一个数组,它的第 i 个元素是这只股票第 i 天的价格。你最多允许完成一次交易(一买一卖),求问你所能获取的最大利润是多少。注意只能先买后卖。这个题有两种做法,一个只是单纯扫描一遍数组来扫描,找到最大的差值;另一个是动态规划。
扫描法是设第一个元素是最低价,然后往后扫描。扫描的时候记住利润 profit = 当前价格 - 最低价。
时间O(n)
空间O(1)
JavaScript实现
1 /** 2 * @param {number[]} prices 3 * @return {number} 4 */ 5 var maxProfit = function (prices) { 6 // corner case 7 if (prices === null || prices.length < 2) return 0; 8 9 // normal case 10 let min = prices[0]; 11 let profit = 0; 12 for (let price of prices) { 13 min = Math.min(min, price); 14 profit = Math.max(profit, price - min); 15 } 16 return profit; 17 };
Java实现
1 class Solution { 2 public int maxProfit(int[] prices) { 3 // corner case 4 if (prices == null || prices.length < 2) { 5 return 0; 6 } 7 8 // normal case 9 int min = prices[0]; 10 int profit = 0; 11 for (int price : prices) { 12 min = Math.min(min, price); 13 profit = Math.max(profit, price - min); 14 } 15 return profit; 16 } 17 }
动态规划的做法如下。设一个二维数组 dp[][] 其中第一维的长度是数组的长度 len,第二维的长度是 2,只有可能是 0 或 1。这里第一维代表的就是遍历到某个位置的 DP 值,第二维表示的是在当前位置是否持有股票。持有记为 1,不持有记为 0。注意这里的不持有不是一直不买,而是卖出之后的不持有。我参考了这个更详细的解释,写的非常好。
这里 DP 值的更新细节如下
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
这一行的意思是在某一个位置如果不持有股票,那么他的DP值有可能是因为上一个位置也是不持有股票,或者是当前位置卖了股票而得到的
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
这一行的意思是在某一个位置如果持有股票,那么他的DP值有可能是因为上一个位置也持有股票,或者是当前位置买了股票导致的。这里为什么买了股票却减prices[i],你可以把这里的负号理解为用户的成本,买了股票自然成本为负了。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int maxProfit(int[] prices) { 3 int len = prices.length; 4 if (len < 2) { 5 return 0; 6 } 7 // 0:用户手上不持股所能获得的最大利润,特指卖出股票以后的不持股,非指没有进行过任何交易的不持股 8 // 1:用户手上持股所能获得的最大利润 9 // 注意:因为题目限制只能交易一次,因此状态只可能从 1 到 0,不可能从 0 到 1 10 int[][] dp = new int[len][2]; 11 dp[0][0] = 0; 12 dp[0][1] = -prices[0]; 13 for (int i = 1; i < len; i++) { 14 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); 15 dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); 16 } 17 return dp[len - 1][0]; 18 } 19 }
相关题目