LeetCode算法题-Best Time to Buy and Sell Stock II

时间:2024-08-28 19:37:38

这是悦乐书的第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)

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