#leetCode刷题纪实 Day21

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
  因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

 

小菜鸡的尝试:

思路比较明确,找到每一段上升段,上升段的起点是买入点,上升段的重点是卖出点。于是开始写代码,然后代码三分钟debug十分钟。思路虽简单,但还是有一些需要注意的细节:

  • 只有在买入了前提才能卖出,只有在卖出以后才能买入
  • 如果传入参数的长度为0或1,直接输出利润为0
  • 注意不等号钟能否取等(容易落下情况)
  • 如果第一天比第二天小,强制性买入
  • 如果到了最后一天还是没有满足卖出条件,强制性卖出
 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int profit = 0;
 5         int inPrice;
 6         int size = prices.size();
 7         int i;
 8         int flag = 0; // 标记是否处于买入状态 (1为买入状态)
 9         if (size == 0 || size == 1) return 0;
10         if (prices[0] <= prices[1]) {
11             inPrice = prices[i];
12             flag = 1;
13         }
14         for (i = 1; i < size - 1; i ++) {
15             if (prices[i - 1] >= prices[i] && prices[i] <= prices[i + 1] && flag == 0) {
16                 inPrice = prices[i];
17                 flag = 1;
18             } else if (prices[i] <= prices[i + 1] && flag == 1) {
19                 continue;
20             } else if (flag == 1){
21                 profit = profit + prices[i] - inPrice;
22                 flag = 0;
23             }
24         }
25         if (flag == 1) {
26             profit = profit + prices[i] - inPrice;
27             flag = 0;
28         }
29         return profit;
30     }
31 };

当然,对这个代码还是不满意,觉得不是很优雅,需要考虑的琐碎情况有点多,于是参看了大佬的代码

 

膜拜大佬代码:

害,我的思路被买卖股票钉死了。虽然大佬的贪心理念和我一样,但他没有被买卖这个操作钉死,所以代码就非常简洁优雅。

虽然利益等于卖出和买入价格差,去掉场景也可以理解为增量值(就是每次增量的总和,因此每每有增量就累计一次,没有增量就不需要累计),简单明了

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

 

 

 

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

上一篇:day21


下一篇:day21【缓冲流、转换流、序列化流】