AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 83. 股票的最大利润    原题链接    简单

作者: 作者的头像   cornerCao ,  2019-01-17 15:51:03 ,  所有人可见 ,  阅读 2279


5


算法1

(遍历) $O(n)$

由于只允许做一次股票买卖交易,枚举每一天作为卖出的日子,买入日子一定在卖出日子之前,为了获利最多,希望买入的日子的股票价格尽可能低。用minnum[i]记录第0-i天的最低价格,则在第i天卖出的最大获利为nums[i]-minnum[i],枚举i找到最大获利。

时间复杂度分析:$O(n)$

C++ 代码

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        vector<int>minnum(nums.size(),0);
        minnum[0] = nums[0];
        for(int i = 1; i<nums.size(); i++){
            if(nums[i]<minnum[i-1])
                minnum[i] = nums[i];
            else
                minnum[i] = minnum[i-1];
        }
        int res = 0;
        for(int i = 0;i<nums.size();i++){
            int delta = nums[i] - minnum[i];
            if(delta > res)
                res = delta;
        }
        return res;
    }
};

2 评论


用户头像
fedfan   2021-04-09 21:08         踩      回复

没有必要开数组记录,0-i的买入的最低价格,用一个变量就行

用户头像
雨_29   2024-06-04 16:13         踩      回复

但感觉这种的会更加容易理解,然后再升级


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息