买卖股票的最佳时机 II
#leetcode #2024/08/09 #算法/股票 #算法/贪心算法
目录
题目及理解
只能买卖一次的场景
前面有讲只能买卖一次的场景，如果能够买卖多次呢？
能够买卖多次的场景：本题
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解题思路
思路一：贪心算法
贪心算法
- 核心思想是：只要今天的价格比昨天高，我们就进行买卖
- 任何上涨的区间分解成若干个相邻两天的小区间
Day 1: 10 ， Day 2: 15 ， Day 3: 20- 我们可以看作是： (20 - 10) = (15 - 10) + (20 - 15)
代码实现
/** 贪心算法：核心思想是只要今天的价格比昨天高，我们就进行买卖
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
// 最大利润
let res = 0;
// 遍历 prices
for (let i = 0; i < prices.length - 1; i++) {
// 如果当前价格比后一天的价格低，就买入，然后卖出
if (prices[i] < prices[i + 1]) {
res += prices[i + 1] - prices[i];
}
}
// 返回最大利润
return res;
};
复杂度分析
- 时间复杂度是
O(n)，其中 n 是价格数组的长度，因为我们只遍历了数组一次。 - 空间复杂度是
O(1)，因为我们只使用了一个额外的变量来存储利润。
思路二：动态规划
这里不展开，此题还是建议使用贪心算法比较合适