LeetCode算法题-Best Time to Buy and

作者: 程序员小川 | 来源:发表于2018-11-16 08:19 被阅读1次

    这是悦乐书的第173次更新,第175篇原创

    01 看题和准备

    今天介绍的是LeetCode算法题中Easy级别的第32题(顺位题号是122)。假设有一个数组,其中第i个元素是第i天给定股票的价格。设计算法以找到最大利润。可以根据需要完成尽可能多的交易(即,多次买入并卖出一股股票)。

    注意:不能同时进行多笔交易(即,您必须在再次购买之前卖出股票)。

    例如:

    输入:[7,1,5,3,6,4]
    输出:7

    说明:在第2天买入(价格= 1)并在第3天卖出(价格= 5),利润= 5-1 = 4。然后在第4天买入(价格= 3)并在第5天卖出(价格= 6),利润= 6-3 = 3。

    输入:[1,2,3,4,5]
    输出:4

    说明:在第1天买入(价格= 1)并在第5天卖出(价格= 5),利润= 5-1 = 4。请注意,您不能在第1天购买,在第2天购买并在以后出售,就像您一样同时参与多个交易。您必须在再次购买之前出售。

    输入:[7,6,4,3,1]
    输出:0

    说明:在这种情况下,不进行任何交易,即最大利润= 0。

    本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

    02 解题

    特殊情况一:当传入的数组为null时,直接返回0。

    特殊情况二:当传入的数组不为null,但是其内只有0个或者1个元素时,无法支持买入并卖出操作,直接返回0。

    正常情况:比之昨天的只能做一次交易,今天这道题可以进行多次交易,来求得最大利润,只要符合低买高卖,利润肯定是会大于0的。如果新的一天的价格比前一天的价格,两者之差就是利润,任意两个相邻的价格只要符合这个规则,都可以算作利润,并且题目也没有说卖出的当天不能再买入,所以依次比较相邻两元素并求差即可。

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

    03 小结

    此题的解法只用了一层循环,因此时间复杂度是O(n);此题只创建了一个变量,因此空间复杂度是O(1)

    以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

    相关文章

      网友评论

        本文标题:LeetCode算法题-Best Time to Buy and

        本文链接:https://www.haomeiwen.com/subject/sfjpfqtx.html