打卡一个力扣题目

简介: 打卡一个力扣题目

关于 ARTS 的释义 —— 每周完成一个 ARTS:

● Algorithm: 每周至少做一个 LeetCode 的算法题

● Review: 阅读并点评至少一篇英文技术文章

● Tips: 学习至少一个技术技巧

● Share: 分享一篇有观点和思考的技术文章

希望通过此次活动能聚集一波热爱技术的人,延续好奇、探索、实践、分享的精神。

一、问题

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。


你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。


返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。


二、解题办法一

def max_profit(prices):
    if not prices:
        return 0
    min_price = prices[0]
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)
    return max_profit


这段代码实现了一个函数 `max_profit`,用于计算在给定的股票价格数组中,选择某一天买入并在未来某一个不同的日子卖出所能获取的最大利润。


首先判断输入的价格数组是否为空,如果为空则直接返回 0。


然后定义两个变量 `min_price` 和 `max_profit`,分别表示当前遍历到的价格中的最低价格和最大利润。初始时将它们都设置为数组的第一个元素。


接下来使用循环遍历整个价格数组,对于每个遍历到的价格,先更新 `min_price` 为当前遍历到的价格和之前记录的最低价格中的较小值,这样可以保证后续计算利润时使用的是更小的价格。


然后计算当前遍历到的价格与 `min_price` 之间的差值,即当前可以选择的利润。将这个利润与之前记录的最大利润比较,取较大值作为新的 `max_profit`。


最后返回 `max_profit` 作为结果。


需要注意的是,这段代码的时间复杂度为 O(n),其中 n 是输入的价格数组的长度。



提示:可简单介绍学习打卡过程中遇到的困难和对应的解决方法~


三、解题方法二

以下是另一种解题思路,使用动态规划的方法实现。

def max_profit(prices):
    if not prices:
        return 0
    n = len(prices)
    dp = [[0] * 2 for _ in range(n)]
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
    return dp[n-1][1]

这段代码中,我们定义了一个二维数组 `dp`,其中 `dp[i][j]` 表示在第 i 天买入并在第 j 天卖出所能获取的最大利润。由于题目要求选择某一天买入并在未来某一个不同的日子卖出,因此我们在计算 `dp[i][j]` 时需要同时考虑两种情况,即在第 i 天买入或在第 i-1 天买入。这样就得到了一个二维的动态规划状态转移方程。


首先初始化 `dp[0][0]` 为 `-prices[0]`,表示如果不进行任何操作,则第一天亏损了价格;初始化 `dp[0][1]` 为 0,表示如果在第一天买入,则第一天没有获得利润。


然后从第 1 天开始遍历到第 n-1 天,对于每个遍历到的天数 i,分别计算在第 i 天买入和在第 i-1 天买入所能获取的最大利润,并取其中的较大值作为当前状态的最优解。具体来说,如果在第 i 天买入,则 `dp[i][0]` 可以取到 `dp[i-1][1] - prices[i]`;如果在第 i-1 天买入,则 `dp[i][1]` 可以取到 `dp[i-1][0] + prices[i]`。最后返回 `dp[n-1][1]` 作为结果。


四、对比分析

这两种方法的时间复杂度都是 O(n),其中 n 是输入的价格数组的长度。因此它们的时间复杂度是相同的,都可以在较短的时间内解决问题。


但是从代码实现的角度来看,这两种方法有一些不同之处。第一种方法使用了循环遍历整个价格数组,并在遍历过程中不断更新最小价格和最大利润。这种方法比较直观,易于理解,但是当价格数组很大时,可能会导致内存占用过高。


第二种方法使用了动态规划的思想,将问题分解为若干个子问题,并通过状态转移方程求解出每个子问题的最优解。这种方法可以有效地减少重复计算,避免了空间复杂度过高的问题。同时,由于动态规划的状态转移方程较为简单,因此代码实现也相对简洁。


综上所述,两种方法各有优缺点,可以根据具体的情况选择适合的方法来解决问题。


相关文章
|
2月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
3月前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
4月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
4月前
|
算法
LeetCode第13题目罗马数字转整数
该文章介绍了 LeetCode 第 13 题罗马数字转整数的解法,通过从大到小解析罗马数字,根据罗马数字的特点,按照从大到小的顺序匹配罗马数字和整数的关系,从而解决该问题,同时强调要注意观察题目考查的知识点特征。
|
6月前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
36 1
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~