力扣经典150题第七题:买卖股票最佳时机

这篇具有很好参考价值的文章主要介绍了力扣经典150题第七题:买卖股票最佳时机。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 简介

本篇博客将讨论力扣经典150题中的买卖股票的最佳时机问题。给定一个数组 prices,其中第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格,我们需要设计一个算法来计算最大利润。

2. 问题描述

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

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

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

示例 1:

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:

1 <= prices.length <= 105
0 <= prices[i] <= 104

3. 解题思路

方法一:一次遍历

利用一次遍历的方法,遍历股票价格数组,同时记录当前最低买入价格和最大利润。

  • 使用变量 minPrice 记录当前遍历过的最低股票价格。
  • 使用变量 maxProfit 记录当前最大利润。
  • 遍历数组,更新 minPricemaxProfit
方法二:动态规划

利用动态规划的思想,定义状态 dp[i] 表示第 i 天的最大利润。

  • 初始状态:dp[0] = 0,表示第一天无利润。
  • 状态转移方程:dp[i] = max(dp[i-1], prices[i] - minPrice),其中 minPrice 表示前 i-1 天的最低股票价格。

4. 算法实现

方法一:一次遍历
public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    return maxProfit;
}
方法二:动态规划
public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n == 0) {
        return 0;
    }
    int minPrice = prices[0];
    int maxProfit = 0;
    for (int i = 1; i < n; i++) {
        minPrice = Math.min(minPrice, prices[i]);
        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }
    return maxProfit;
}

5. 示例与测试

我们使用示例输入进行测试,并验证算法的正确性:

int[] prices1 = {7, 1, 5, 3, 6, 4};
int[] prices2 = {7, 6, 4, 3, 1};

System.out.println("Test Case 1:");
System.out.println("Expected Result: 5");
System.out.println("Actual Result: " + maxProfit(prices1));

System.out.println("Test Case 2:");
System.out.println("Expected Result: 0");
System.out.println("Actual Result: " + maxProfit(prices2));

输出结果为:

Test Case 1:
Expected Result: 5
Actual Result: 5

Test Case 2:
Expected Result: 0
Actual Result: 0

6. 总结与展望

通过本篇博客,我们详细讨论了力扣经典150题中的买卖股票的最佳时机问题,并提供了两种解题方法的实现。这些方法都具有高效性和简洁性,在实际应用中具有广泛的适用性。

7. 结语

希望本文能够帮助大家更好地理解和掌握买卖股票的最佳时机的解题思路和实现方法,欢迎提出您的宝贵意见和建议。文章来源地址https://www.toymoban.com/news/detail-849930.html

到了这里,关于力扣经典150题第七题:买卖股票最佳时机的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 买卖股票的最佳时机【力扣121】

    假如我们要在第 i 天卖出股票,那么为了获得最大利润,买股票的最佳时间是第 i 天前的最低股价的那一天。 我们使用min来记录已经访问过的 0-i 天的最低股价。那么在第 i 天,如果股价大于min,那么最大利润为price[i]-min;否则最大利润为0,并且min=price[i]。

    2024年02月11日
    浏览(41)
  • 力扣 121. 买卖股票的最佳时机

    题目来源:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/ 好久没写代码了,啥啥都忘了 C++题解1:贪心算法。(来源代码随想录) 因为股票就买卖一次,那么贪心的想法很自然就是取最左最小值,取最右最大值,那么得到的差值就是最大利润。 时间复杂度:O(n) 空

    2024年02月20日
    浏览(33)
  • 力扣 188. 买卖股票的最佳时机 IV

    题目来源:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/ C++题解:动态规划 思路同力扣 123. 买卖股票的最佳时机 III-CSDN博客,只是把最高2次换成k次。如果思路不清晰,可以将k从0写到4等找找规律。

    2024年02月20日
    浏览(37)
  • 力扣122. 买卖股票的最佳时机 II

    思路: 假设 dp[i][0] 是第 i 天手上没有股票时的最大利润, dp[i][1] 是第 i 天手上有 1 支股票的最大利润; dp[i][0] 的迁移状态为: dp[i - 1][0],前一天手上已经没有股票,没有发生交易; dp[i - 1][1] + prices[i],前一天手上有 1 支股票,第 i 天将其卖掉获得收益 prices[i]; 所以,

    2024年02月03日
    浏览(40)
  • 力扣(Leetcode) 121. 买卖股票的最佳时机

    给定一个数组  prices  ,它的第  i  个元素  prices[i]  表示一支给定股票第  i  天的价格。 你只能选择  某一天  买入这只股票,并选择在  未来的某一个不同的日子  卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如

    2024年01月25日
    浏览(41)
  • 力扣 -- 309. 最佳买卖股票时机含冷冻期

     题目链接:309. 最佳买卖股票时机含冷冻期 - 力扣(LeetCode) 下面是用动态规划的思想解决这道题的过程,相信各位小伙伴都能看懂并且掌握这道经典的动规题目滴。   参考代码:  以上就是用动态规划的思想分析这道题目的整个过程啦,你学会了吗?如果以上题解对你有

    2024年02月13日
    浏览(37)
  • 力扣经典150题第三十题:长度最小的子数组

    1. 介绍 在本篇文章中,我们将解析力扣经典150题中的第三十题:长度最小的子数组。题目要求找出数组中满足其总和大于等于目标值 target 的长度最小的连续子数组,并返回其长度。 2. 问题描述 给定一个含有 n 个正整数的数组 nums 和一个正整数 target ,找出该数组中满足其总

    2024年04月23日
    浏览(48)
  • 力扣 309. 买卖股票的最佳时机含冷冻期

    题目来源:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/ C++题解:动态规划 状态1:表示持有股票。更新为之前持有股票(dp[i-1][0])或者不持有股票且不处于冷冻期后买入(dp[i-1][2]-prices[i])。 状态2:表示不持有股票且处于冷冻期,即卖出。更新为持有

    2024年02月22日
    浏览(32)
  • 力扣 -- 714. 买卖股票的最佳时机含手续费

    题目链接:714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)  下面是用动态规划的思想解决这道题的过程,相信各位小伙伴都能看懂并且掌握这道经典的动规题目滴。 参考代码:   以上就是用动态规划的思想分析这道题目的整个过程啦,你学会了吗?如果以上题解对你有

    2024年02月13日
    浏览(35)
  • dp算法 力扣309最佳买卖股票时机含冷冻期

    给定一个整数数组prices,其中第  prices[i] 表示第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 注意:你不能同时参与多笔交

    2024年02月14日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包