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

leetcode_121 买卖股票的最佳时期

1. 题意

有一个股价变化图,你可以在一天买入,在未来一天卖出。

求通过这样一次操作的最大获利。

2. 题解

2.1 枚举

直接枚举,买入卖出的时间,肯定会超时啦~

时间复杂度为O(n2)O(n^2)O(n2)
空间复杂度为O(1)O(1)O(1)

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

我们不难想到,我们每次卖股票的时候,只需要买入当前股票之前最低股份的股票就可以了!因此我们可以边统计最低股价,一边计算差值的最大值。

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int ans = 0;int mn = prices[0];for (int i = 1; i < n; ++i) {ans = max(prices[i] - mn, ans);mn  = min(mn, prices[i]);}return ans;}
};
2.3 动态规划

动态规划的思路和贪心的感觉差不多,也不知道这算不算动态规划~

我们用dp[i]dp[i]dp[i]表示卖出的股票是prices[i]prices[i]prices[i]时的最大差值。

因此ans=max⁡{dp[i]∣1≤i≤prices.size()−1}ans=\max \left\{dp[i]\ \Big |\ 1\le i \le prices.size()-1 \right\}ans=max{dp[i]  1iprices.size()1}

同样对于dp[i]dp[i]dp[i],我们需要知道iii之前的最小股份,所以最终代码跟

贪心差不多?空间优化完后,代码估计就跟贪心一样,就不写了。

class Solution {
public:int maxProfit(vector<int>& prices) {int n   = prices.size();int ans = 0;vector<int> dp(n + 1, 0);int mn = prices[0];for (int i = 0;i < n; ++i) {dp[i + 1] = max( dp[i], prices[i] - mn);mn = min( prices[i], mn);}return dp[n];}
};
2.4 差分+动态规划

这个题目跟lc53 最大子数组和, 是相互变形的关系。

其实也就是差分和前缀和的关系。

lc53可以通过前缀和转换成这个问题,当然这个问题也可以通过差分变成

最大子数组和。贴个代码吧,也懒得再解释了OvO

class Solution {
public:int maxProfit(vector<int>& prices) {adjacent_difference( prices.begin(), prices.end(), prices.begin());prices[0] = 0;int ans = 0;int pre = 0;for (auto v: prices) {pre += v;ans = max( pre, ans);if (pre < 0)pre = 0;}return ans;}
};
http://www.xdnf.cn/news/1153261.html

相关文章:

  • AWS Partner: Accreditation (Technical)
  • 轻松上手:从零开始启动第一个 Solana 测试节点
  • 综合实验--eNSP实验
  • TypeScript 泛型详解:从基础到实战应用
  • Linux中添加重定向(Redirection)功能到minishell
  • python网络爬虫之selenium库(二)
  • 【Web APIs】JavaScript 自定义属性操作 ② ( H5 自定义属性 )
  • 图片放大镜案例
  • Patch-wise Structural:一种引入局部统计特性的时序预测损失函数
  • CS231n-2017 Lecture3线性分类器、最优化笔记
  • QT窗口(7)-QColorDiag
  • [spring6: AspectJAdvisorFactory AspectJProxyFactory]-源码解析
  • Linux C 信号操作
  • “外卖大战”正在改变国内“大零售”
  • 图解系统-小林coding笔记
  • 骑行邂逅LV巨轮,VELO维乐Angel Rise坐垫与时尚超适配
  • YOLOv11改进 | RFAConv重塑空间注意力助力性能提升
  • 开关电源和线性电源Multisim电路仿真实验汇总——硬件工程师笔记
  • 使用UV管理FastAPI项目
  • HOT100——动态规划篇Leetcode221. 最大正方形
  • 模型自信度提升:增强输出技巧
  • 纸板制造糊机操作
  • Datawhale AI数据分析 作业
  • 基于朴素贝叶斯的姓名性别预测系统
  • Ubuntu20.04 samba配置
  • 2023年CSP入门级第二轮第四题——旅游巴士
  • 马走日题解
  • Apache Kafka 学习笔记
  • 手撕Spring底层系列之:注解驱动的魔力与实现内幕
  • Node.js dns 模块深入解析