首页 > 其他分享 >【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 买卖股票的最佳时机

【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 买卖股票的最佳时机

时间:2024-11-06 22:46:31浏览次数:3  
标签:sell buy int 40 maxResult prices leetcode best

买卖股票系列

【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 买卖股票的最佳时机

【leetcode】41-best-time-to-buy-and-sell-stock-ii 力扣 122. 买卖股票的最佳时机 II

【leetcode】42-best-time-to-buy-and-sell-stock-iii 力扣 123. 买卖股票的最佳时机 III

【leetcode】43-best-time-to-buy-and-sell-stock-iv 力扣 188. 买卖股票的最佳时机 IV

【leetcode】44-best-time-to-buy-and-sell-stock-with-cooldown 力扣 309. 买卖股票的最佳时机包含冷冻期

【leetcode】45-best-time-to-buy-and-sell-stock-with-cooldown 力扣 714. 买卖股票的最佳时机包含手续费

开源地址

为了便于大家学习,所有实现均已开源。欢迎 fork + star~

https://github.com/houbb/leetcode

121. 买卖股票的最佳时机

给定一个数组 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 <= 10^5
0 <= prices[i] <= 10^4

V1-暴力解法

    /**
     * 最简单的暴力算法
     * @param prices 价格
     * @return 结果
     */
    public int maxProfit(int[] prices) {
        int maxResult = 0;

        for(int i = 0; i < prices.length-1; i++) {
            for(int j = i+1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                maxResult =  Math.max(profit, maxResult);
            }
        }

        return maxResult;
    }

这种解法会超时。

v2-如何优化呢?

核心的一点:最大的利润,卖出之前则必须是买入的最小值、卖出的最大值。

所以只需要做几件事:

0)最大值,最小值初始化为 prices[0];

1)记录最大的利润 maxResult = maxPrice - minPrice;

2)如果遇到了最小值,则重新初始化 minPrice, maxPrice

代码实现

    public int maxProfit(int[] prices) {
        int maxResult = 0;
        int minVal = prices[0];
        int maxVal = prices[0];
        for(int i = 1; i < prices.length; i++) {
            int cur = prices[i];
            // 值大于当前值
            if(cur > maxVal) {
                maxResult = Math.max(maxResult, cur - minVal);
            }
            // 重置
            if(cur < minVal) {
                minVal = cur;
                maxVal = cur;
            }
        }

        return maxResult;
    }

V2.5-代码性能优化

优化思路

上面的分支判断太多

核心实现

class Solution {

    public int maxProfit(int[] prices) {
        int maxResult = 0;
        int minVal = prices[0];
        for(int i = 0; i < prices.length; i++) {
            minVal = Math.min(minVal, prices[i]);
            maxResult = Math.max(prices[i] - minVal, maxResult);
        }

        return maxResult;
    }
    
}

效果

1ms 击败100.00%

V3-DP 的思路-贯穿整体解法

思路

我们一共完成了一笔完整的交易,分为两步:

  1. b1 买入1
  2. s1 卖出1

卖出+买入构成了完整的交易。

每一天我们都可以决定是否买,是否卖?

初始化

b1 买入时,我们初始化为 -prices[0];

s1 卖出时,初始化为0;

代码

public int maxProfit(int[] prices) {
    int b1 = -prices[0];
    int s1 = 0;

    for(int i = 0; i < prices.length; i++) {
        // 卖出第一笔 是否卖?  不卖则为s1, 卖出则为 b1 + prices[i]
        s1 = Math.max(s1, b1 + prices[i]);
        // 买入第一笔 是否买?  如果买,则花费为当前金额;
        b1 = Math.max(b1, - prices[i]);
    }
    return s1;
}

标签:sell,buy,int,40,maxResult,prices,leetcode,best
From: https://www.cnblogs.com/houbbBlogs/p/18531219

相关文章

  • 找不到mfc140u.dll,无法继续执行代码的原因分析与解决方案
    mfc140u.dll是MicrosoftFoundationClasses(MFC)库的一部分,它是VisualStudio2015中的一个重要组件。MFC提供了一组预定义的类和函数,用于简化Windows应用程序的开发过程。mfc140u.dll文件包含了这些类和函数的实现,许多基于MFC开发的应用程序依赖于它来正常运行。......
  • 找不到msvcp140.dll无法继续执行代码是什么意思,如何修复
    msvcp140.dll是MicrosoftVisualC++库中的关键组件,具体而言,它是随MicrosoftVisualC++Redistributable包提供的动态链接库(DLL)文件。这一文件对于Windows操作系统中的应用程序至关重要,因为它包含了运行由VisualStudio2015或更高版本编译的C++应用程序所需的运行......
  • ssm在线教育系统-计算机毕业设计源码14087
    目录摘要1绪论1.1选题背景与意义1.2国内外研究现状1.3论文结构与章节安排2系统分析2.1可行性分析2.2系统流程分析2.2.1系统开发流程2.2.2用户登录流程2.2.3系统操作流程2.2.4添加信息流程2.2.5修改信息流程2.2.6删除信息流程2.3 系统......
  • springboot高校医务室管理系统-计算机设计毕业源码58407
    目 录摘 要1绪论1.1研究背景与意义1.2国内外研究现状1.3论文结构与章节安排1.4相关技术、工具简介2 高校医务室管理系统项目概述2.1可行性分析2.1.1技术可行性2.1.2 经济可行性2.1.3操作可行性2.2 系统功能分析2.2.1功能性分析2.2.2......
  • 20222408 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容1.1实验要求(1)对恶意代码样本进行识别文件类型、脱壳、字符串提取操作。(2)使用IDAPro静态或动态分析所给的exe文件,找到输出成功信息的方法。(3)分析恶意代码样本并撰写报告,回答问题。(4)对于Snort收集的蜜罐主机5天的网络数据源进行分析,回答问题。1.2学习内容恶意代码......
  • 20222404 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1基本概念1.1恶意代码恶意代码(MaliciousCode)是指以技术炫耀/恶作剧,远程控制,窃取私密信息,盗用资源,拒绝服务/破坏等为目的,使计算机按照攻击者的意图运行以达到恶意目的的指令集合。类型包括计算机病毒、蠕虫、特洛伊木马、逻辑炸弹、系统后门、Rootkit、僵尸程序等。1.2......
  • 20222405 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容(1)恶意代码文件类型标识、脱壳与字符串提取(2)使用IDAPro静态或动态分析crackme1.exe与crakeme2.exe,寻找特定输入,使其能够输出成功信息。(3)分析一个自制恶意代码样本rada,并撰写报告,回答问题(4)取证分析实践2.实验过程2.1恶意代码文件类型标识、脱壳与字符串提取(1)使用......
  • Dell 塔式t440 安装centos
    硬件介绍1个10核2个超线程数cpu、cpu型号为4210R、内存大小为32G、两块1T硬盘、一张软阵列卡S140安装过程点击查看安装过程1.开机按F2进入SystemSetup界面,进入SystemBiosSettings界面1.1.SystemBiosSettings->SATASettings->选择【ACHIMode】......
  • 20240719 CVTE 笔试
    岗位:嵌入式软件开发工程师(Linux方向)题型:20道不定项选择题,2道编程题1、不定项选择题1.1如下哪个命令可以帮助你知道shell的用法(D)morehelppwdman解答:more,以翻页的形式查看某文件中的内容help,无此命令pwd,显示当前工作目录的完整路径man,查看命令的手册页,因此选......
  • 玉米品种近40年来累计推广面积前20强及年度前10强排行榜
    一粒小小的玉米种子凝聚了育种家和种业企业推广的心血。1949年起,我国玉米育种经历了地方品种改良、双交种、单交种3个发展时期。在单交种时期,玉米育种又经历了6次大规模的品种更新换代。建国70年来,我国玉米面积增加3.26倍,单产提高6.35倍,总产增长21.42倍,玉米育种对产量增加的贡献极......