首页 > 代码库 > 122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II

2024-08-19 20:25:25   220人阅读

　　不定期更新leetcode解题java答案。

　　采用pick one的方式选择。

　　由于随机到了系列问题，在此继续做后序版本。

　　题意为给定一个数组，数组分别表示当天物品的售价，允许多次买卖（卖的前提是买，买的前提是卖，也就是身上没有物品时才可以买），问最大的收益是多少。

　　首先的分析方式就是，我们应该在什么时候买，在什么时候卖。

　　试想，当我们购买了物品，隔天如果涨价了，我们不卖，要看第三天的价格是不是比第二天低；如果降价了，那么我们应该在第二天买，再进行判断。这个步骤可以换成逻辑为：

　　我们今天购买了物品，第二天涨价了，需要进行第三天的判断；如果降价了，那么我们应该在前一天卖掉，在第二天买进（同上段，如果刚买入第二天就降价，那么就在买入当天卖掉，也就等同于第一天不买入）。由上述分析可得如下代码：

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         if(prices.length == 0)
 4             return 0;
 5 
 6         int profit = 0, buyPrice = prices[0];
 7         
 8         for(int i = 1; i < prices.length; i++){
 9             if(prices[i] < prices[i - 1]){
10                 profit += prices[i - 1] - buyPrice;
11                 buyPrice = prices[i];
12             }
13         }
14         //由于循环的最后有可能没有执行卖出的操作
15         profit += prices[prices.length - 1] - buyPrice;
16         
17         return profit;
18     }
19 }

　　同样的，python代码如下：

 1 class Solution(object):
 2     def maxProfit(self, prices):
 3         """
 4         :type prices: List[int]
 5         :rtype: int
 6         """
 7         if len(prices) == 0:
 8             return 0;
 9         profit = 0
10         buyPrice = prices[0]
11         lastPrice = prices[0]
12         
13         for price in prices:
14             if lastPrice > price:
15                 profit += lastPrice - buyPrice
16                 buyPrice = price
17                 
18             lastPrice = price
19         
20         profit += prices[len(prices) - 1] - buyPrice
21         
22         return profit

 

　　当然，我们可以换一种思考的方式，利用贪心法，只要第二天比第一天的价格高，那么我们就在今天买，第二天卖出，获取局部最优解，以达到最终最大收益。这种想法由于没有前文的多天卖出的判定条件（第三天比第二天低），循环后不需要再补充代码，具体代码如下：

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         int profit = 0;
 4         
 5         for(int i = 1; i < prices.length; i++)
 6             if(prices[i] > prices[i - 1])
 7                 profit += prices[i] - prices[i - 1];
 8 
 9         return profit;
10     }
11 }

　　对应python代码如下：

 1 class Solution(object):
 2     def maxProfit(self, prices):
 3         """
 4         :type prices: List[int]
 5         :rtype: int
 6         """
 7         if len(prices) == 0:
 8            return 0
 9         lastPrice = prices[0]
10         profit = 0
11         for price in prices:
12             if price > lastPrice:
13                 profit += price - lastPrice
14             lastPrice = price
15         return profit

 

122. Best Time to Buy and Sell Stock II


联系
我们