数据结构002:买卖股票的最佳时机
2023-02-18 15:50:13 时间
题目
给定一个数组 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。
解题思路
结合题意,想获取高额回报,肯定是低买高卖,那我们首先想到的是找出数组中的最小值,当天买入,找出最大值,当天卖出,岂不美哉,但是两个字立马把我们拉回现实,如果数组的最大值在最小值前面呢,不就不符合实际情况了吗。那我们该怎么搞?突然想到这道题与我们之前的最大子数组和的内容有些类似,那解题思路是否类似呢?我们套用一下它的思路,找软柿子捏,先从短的数组开始分析(以{a, b, c, d, e}为例),既然要从短的数组分析,为了找出规律,我们将
记为第
天卖出股票时的最大利润。那么,我们需要在[0,i-1]的范围内找到最小值
,则有
。
- i=0:题目要求当天买入,只能在未来的日子卖出。因此,无法在
处卖出,因此,最小值
,
。
- i=1:这种只能
处买入,
处卖出。最小值
,
。
- i=2:最小值
,
。
- i=3:最小值
,
。
- i=4:最小值
,
。
上面我们已经把prices = {a, b, c, d, e}中,第
天卖出股票的所有情况都列举出来了,那么要求一次交易获取的最大利润
就变得很简单了:
结合上面的分析,该问题的实现代码应该如下:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = numeric_limits<int>::max(); //将minPrice初始化为一个int型最大值,同时兼容i=0时的情况
int maxProfit = 0;
for (int price: prices) {
maxProfit = max(maxProfit, price - minPrice);
minPrice = min(price, minPrice); //对应minPrice[0,i)=max{minPrice[0,1-1), prices[i-1]}
}
return maxProfit;
}
};
上述代码,只进行了一次循环,因此其时间复杂度为O(n) ,空间上,用了常数个变量,空间复杂度为O(1) .
相关文章
- 【架构师(第十五篇)】脚手架之创建项目模板开发
- 【架构师(第十六篇)】脚手架之创建项目模板的下载与更新
- 【架构师(第十八篇)】脚手架之项目模板的安装
- 【架构师(第十九篇)】脚手架之组件库模板开发
- 【架构师(第二十篇)】脚手架之自定义模板及第一阶段总结
- 【架构师(第二十一篇)】编辑器开发之需求分析和架构设计
- 【架构师(第二十二篇)】编辑器开发之项目整体搭建
- 【架构师(第二十三篇)】编辑器开发之画布区域组件的渲染
- 【架构师(第二十四篇)】编辑器开发之添加模版到画布
- Java异常处理:如何写出“正确”但被编译器认为有语法错误的程序
- 我以订披萨为例,给女朋友详细讲了Java设计模式的3种工厂模式
- 【架构师(第二十五篇)】编辑器开发之属性编辑区域表单渲染
- 【架构师(第二十六篇)】编辑器开发之属性编辑同步渲染
- 2021年度“CCF-腾讯犀牛鸟基金”发布结题评优结果
- 【架构师(第二十七篇)】前端单元测试框架 Jest 基础知识入门
- 太空噗|重燃太空热潮!与噗噗星人一同探索星海浪漫
- 算法工程师深度解构ChatGPT技术
- 【架构师(第二十八篇)】 测试工具 Vue-Test-Utils 基础语法
- 【架构师(第二十九篇)】Vue-Test-Utils 触发事件和异步请求
- 【架构师(第三十篇)】Vue-Test-Utils 全局组件和第三方库 vuex | vue-router