X

LEETCODE 122. Best Time to Buy and Sell Stock II 解题思路分析

题目大意:

买卖股票的最佳时机 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。

提示:

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=122

解题思路分析:

(第一段为废话杂谈,可略过)

看到股票价格曲线,让我想到了K线图,我平日里最大的爱好就是钻研各种k线理论,然后再利用我这一知半解的技术挤进金融市场里去当韭菜。这里说几句题外话,如果你是一位初级投资爱好者,我在这里可以跟你分享一个经验,不论投资股票,基金,外汇或是加密货币等,一定要做价值投资,长线投资那些具有长远价值的产品才不会被狗庄当做棋子任意摆布。任何短线操作都像是赌博,即是你的k线技术再高超,也抵不过狗庄们的一次次画门插针操作,短线止损的次数多了,你就会失去理智,下单都带着赌气的心理,直到一次一次被市场玩弄,你才发现,股票的价格没变,自己的钱却都没了。因此以长线投资为主,短线投机相佐的策略才是正道。比如我坚信比特币在未来2年内会涨到5-10w刀一枚,那么现价(9000多刀)我会毫不犹豫的买入,也许未来几个月它的价格会像过山车一般翻来覆去,但这都与我无关,2年后才是我的收获日。

回到本题,题目要求获得最大利益,实际上是让我们站在上帝的视角来操盘股市,进行抄底逃顶操作。我们遍历数组中每一个数,如果当前数字大于前一位上的数字,说明相比于昨天,今天的股票价格出现了上涨,那么我们可以穿越回昨天买入,然后再回到今天卖出,买卖的差价累加至总利益。循环完所有的天数后,总利益即是返回答案。

当然本题也可以先统计出价格曲线中所有的波峰与波谷,用所有的波峰减去相邻的前一个波谷价格,这两种解法的时间复杂度都是O(1),这里就不过多介绍了。

实现代码:

public int maxProfit(int[] prices) {
    int sum=0;
    for(int i=1;i<prices.length;i++){
        if(prices[i]>prices[i-1]){
            sum+=prices[i]-prices[i-1];
        } 
    }
    return sum;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 93.55% of Java online submissions for Best Time to Buy and Sell Stock II.

Memory Usage: 39.7 MB, less than 11.43% of Java online submissions for Best Time to Buy and Sell Stock II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-122-best-time-to-buy-and-sell-stock-ii-解题思路分析/
Categories: leetcode
kwantong: