当前位置: 首页 > news >正文

每日一题 ###121买卖股票的最佳时机

仅以此记录所学所想,如有错误,还望指正。

首次尝试

1、我小小的脑子只能想出暴力解法,结果是超时了。

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

我也知道肯定是两层for循环,O(n^2)的时间复杂度遭了。但是我想不明白如何只用一次遍历解决问题。思考五分钟,跑去看题解了。(下次多思考会儿)

题解

class Solution {
public:int maxProfit(vector<int>& prices) {int minprice=1e5;int maxprofit=0;for(int price:prices){maxprofit=max(maxprofit,price-minprice);minprice=min(minprice,price);}return maxprofit;}};
解题思路:

1、一次遍历+贪心,动态记录最小值和最大利润。每次都假设当天卖出,利润最大是当天价-之前最低的价格。再用这个利润和历史最高利润比较,取最大值。
2、先maxprofit,后minprice,是因为顺序倒置后,第一天就会出问题,最低价是自己,利润为0,同天买入卖出。

学习收获:

1、第一次看for(int price:prices)这种语法,之前一直没用过。
2、感觉自己无法独立想出这种好方法啊,急需解决。

http://www.hskmm.com/?act=detail&tid=28348

相关文章:

  • 10.10总结
  • LibreChat-图文并茂手把手教你界面配置 | Adorable LibreChat Interface Configuration Guide
  • GAE-广义优势估计算法介绍
  • qemu模拟单片机
  • RAG-检索增强生成
  • “猴子补丁”(monkey patch)跟猴子有关吗?
  • Yapi 使用docker在cenos7上部署教程与基本使用
  • C语言vsC++
  • 20251010 之所思 - 人生如梦
  • 2025.10.10
  • 个人书单-从心流出发,学习积极心理学
  • 等号(=)在C语言和python中有什么区别?
  • AI元人文(十四)之价值共生篇:再论物物交换——作为价值共生基础的元协议
  • 4.布局系统
  • Python clickhouse-driver 类库使用学习总结
  • 虚拟环境QA
  • 计算机系统知识 - 呓语
  • 详解 `a, b = b, a + b`:执行逻辑、常见误区与赋值符号辨析
  • xdown 全能下载
  • 2025.10.10 - 20243867孙堃2405
  • 密码系统设计
  • c#服务安装和卸载等等
  • 进制表示
  • 在AI技术快速实现创意的时代,挖掘用户真实需求成为关键——某知名电池管理工具需求洞察
  • 从梯度提升树到分布式机器学习算法
  • iPhone手机越狱后出现闪退的解决方法
  • 企业推行 OKR 的 10 个关键问题
  • 读《构建之法》后的六个问题
  • 自动输入小程序
  • 实用指南:基于阿里云系列平台的python微服务设计与DevOps实践