每日算法系列【LeetCode 122】买卖股票的最佳时机 II

简介: 每日算法系列【LeetCode 122】买卖股票的最佳时机 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 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

题解

这是 【买卖股票的最佳时机】 系列题目的第二题。

这题买卖次数变成了不限,但是仍然要求在买之前必须先卖掉股票。那么观察股票的价格曲线,最优策略就是在每一段单调上升的子区间里,区间开始时购买,区间结束时卖出。这样就能保证所有的上升区间全部充分利用到了。正确性证明也不难,假设买卖过程中包含了一段下降的子区间,那么去掉它,在下降区间开头卖出,在下降区间末尾买入,得到的利润一定大于包含这段下降区间。

在具体实现时,我们可以计算相邻两个股票价格差,如果价格是上升的,那就在利润上加上它,否则就不用管。

最终的答案就是:

时间复杂度是  。

代码

python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n, res = len(prices), 0
        for i in range(1, n):
            res += max(prices[i]-prices[i-1], 0)
        return res
目录
打赏
0
0
0
0
14
分享
相关文章
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
4月前
|
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
48 2
|
4月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
59 0
|
6月前
|
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
81 0
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
69 1
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
94 1
|
6月前
|
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
81 6
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
99 0
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
101 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口