LC121. 买卖股票的最佳时机

题目描述

这是 LeetCode 上的(121. 买卖股票的最佳时机) ,难度为 简单

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

示例 1:

1
2
3
4
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

1
2
3
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0

提示:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

题解

贪心

  • profit (最大利润)
  • cost (最小成本)
  • cost 记录 与历史最低成本相比最低成本
  • profit 记录 与历史最高利润相比最高利润
  • 由于profit是由 今天价格-历史最低成本历史最高利润 进行比较,不会出现 过去最高价格卖,今天最低价格买 的情况

1658590330-wivils-figures.gif

代码

[贪心]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int maxProfit(vector<int>& prices) {
int cost = INT_MAX;
int profit = 0;
for(int price : prices){
cost = min(cost, price);
profit = max(profit, price - cost);
}
return profit;
}
};

复杂度

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

最后

最简题解来自于leetcode 121. 买卖股票的最佳时机(动态规划,清晰图解)

我的代码

  • mpa = max profit array 最大利润数组
  • mic = min cost 最小成本
  • res 最大利润
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
int mpa[len];
int mic = prices[0];
int res = 0;
for(int i = 1; i < len; i++){
mic = mic < prices[i] ? mic : prices[i];
mpa[i] = prices[i] - mic;
res = res > mpa[i] ? res : mpa[i];
}
return res;
}
};

LC121. 买卖股票的最佳时机
https://blog.daynoti.com/posts/49437/
作者
Alan White
发布于
2024年4月24日
更新于
2024年7月1日
许可协议