(LeetCode-数组-1) 买卖股票的最佳时机[通俗易懂]

(LeetCode-数组-1) 买卖股票的最佳时机

大家好,又见面了,我是全栈君。

1.买卖股票的最佳时机

假设你有一个数组,其中第 i 个元素是一支给定股票第 i 天的价格。如果您只能完成最多一笔交易(即买入和卖出一股股票),则设计一个算法来找到最大的利润。

输入: [7, 1, 5, 3, 6, 4]
输出: 5

最大利润 = 6-1 = 5(不是 7-1 = 6, 因为卖出价格需要大于买入价格)

分析:
1.只能交易一笔
2.变量current为买入价格,max为最大利润
3.低则买入,高则卖出

int maxProfit(vector<int>& prices) {
        if(prices.empty())return 0;
        int max=0,current=prices[0];
        for(int i=1;i<prices.size();i++){
        if(current>prices[i]){
            current=prices[i];
        }else{
            int sum=prices[i]-current;
            if(sum>max)max=sum;
        }
        }
        return max;
}

2.买卖股票的最佳时机 II

假设有一个数组,它的第 i 个元素是一个给定的股票在第 i 天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。

分析:
1.可以交易多笔
2.相邻价格中,只要后一次比前一次高,就买入

int maxProfit(vector<int>& prices) {
     if(prices.empty())return 0;
       int max = 0;
       for(int i=1; i<prices.size(); i++) {
         if(prices[i] - prices[i-1] > 0) {
              max += (prices[i] - prices[i-1]);
         }
     }
     return max;
}

3.买卖股票的最佳时机 III

假设你有一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。你不可同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

分析:
1.最多可以进行两笔交易
2.将数组分为左右两个子数组,分别求出对应的最大利润

int maxProfit(vector<int>& prices) {
            if(prices.empty())return 0;
            int min=prices.front(),max=prices.back(),size=prices.size();
            vector<int> left(size,0);
            vector<int> right(size,0);
            for(int i=1;i<size;i++){
            if(prices[i]>min){
                left[i]=(prices[i]-min)>left[i-1]?(prices[i]-min):left[i-1];
            }else{
                left[i]=left[i-1];
                min=prices[i];
            }
    }
    for(int i=size-2;i>=0;i--){
        if(prices[i]<max){
            right[i]=(max-prices[i])>right[i+1]?(max-prices[i]):right[i+1];
        }else{
            right[i]=right[i+1];
            max=prices[i];
        }
    }
    int result=0;
    for(int i=0;i<size;i++){
        result=(right[i]+left[i])>result?(right[i]+left[i]):result;
    }
    return result;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107604.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • git 迁出/克隆远程仓库的指定分支方法(附常用git配置命令)

    普通克隆方式:gitclone&lt;远程仓库地址&gt;这种克隆方式默认是克隆master主分支,而且通过命令gitbranch–list能看到克隆后在本地也只有这一个分支,如果再通过新建分支再拉取指定分支,甚至可能还需要解决冲突,太繁琐。那么,如何快速有效的直接克隆远程指定分支?只需要一条命令:gitclone-b&lt;指定分支名&gt;&…

  • react mock_vue mock数据

    react mock_vue mock数据前言在开发项目时,前端需要和后端对接数据,但有时后端并没有写好数据,前端还需要继续往下开发,这时候就需要mock数据了。如何mock数据?如下代码,在input获得焦点时调用getList()方法。constmapDispathToProps=(dispatch)=>{return{handleInputFocus(){…

    2022年10月29日
  • 产生随机数算法[通俗易懂]

    产生随机数算法[通俗易懂]两个办法帮你解决如何在Java中产生随机数http://cd.qq.com     随机数在日常的应用和开发中经常会见到,比如说某些系统会为用户生成一个最初的初始化密码,这就是一个随机数。如何生成这个随机数,不同的开发工具的方法也不一样。在应用中,Java是应用最为广泛的开发工具之一,如何在Java中产生随机数,也是很多开发者在初学随机数时的一个必修课,在此为读者贡献两个办法帮你

  • 服务器硬件基础知识

    服务器硬件基础知识服务器的概述计算机的硬件主要有主机和输入/输出设备。主机包括机箱,电源,主板,CPU(中央处理器),内存,显卡,声卡,网卡,硬盘,光驱等。输入/输出包括显示器,键盘,鼠标,音箱,摄像头,打印机和扫描仪等。服务器服务器是指在网络环境下运行相应的应用软件,为网上用户提供共享信息资源和各种服务的一直高性能计算机。服务器的选择:处理器性能,I/O性能,管理性,可靠性,扩展性。同样…

  • 增长思维和增长黑客_黑客手册中文版

    增长思维和增长黑客_黑客手册中文版原书:《增长黑客手册——如何用数据驱动爆发式增长》点击图片可放大查看(放大后上下滑动查看)

  • MFC之COleVariant类

    MFC之COleVariant类COleVariant本质上是一个枚举,用同一种类型来表达不同的子类型。如同boost中的variant。 COleVariant类是对VARIANT结构的封装。  VARIANT结构包含两部分。其一是VARTYPE型的成员变量vt;其二是个联合类型,这个联合包含了VC常用的几乎所有类型。因为联合用的是相同的存储空间,因此对联合的内容的解释依赖于vt。  例如,  若vt的…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号