股票的最大利润
题目描述
假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?
示例:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
0 <= 数组长度 <= 10^5
题目分析
说起股票,最近可是亏大了,癌股啊癌股~
回归正题,这题的暴力做法是每一个数都和后面的数做差值,然后得出利润最大的数,也就是差值最大的正数,时间复杂度是O(N2),那优雅一点的做法时间复杂度一定得小于暴力法吧;下面就来讲讲优雅一点的做法:
演示例子:[7,1,5,0,6,4]
- 第一天:现在只知道今天的股价是7块一股,所以第一天的最佳买入价格是7(啊蛇,我眸得捡啊),最大盈利是0(因为还没卖)
- 第二天,今天的股市大跌,股价掉到了1块一股,所以前两天最佳的买入价格是1,最大利润是0,因为第二天比第一天要便宜,卖出去岂不是血亏
- 第三天,今天的股市稍微回暖,涨到了5块一股,那前三天里最佳购买的价格还是1,因为5比1大嘛,所以第三天卖出的话能稳赚4,所以现在的最大利益是4
- 第四天,一般来说股市回暖后都会继续割韭菜的,所以又跌到了0,之前最适合买入的是1,现在是0,所以在从现在开始最适合买入的变成0了,白嫖嘛
- 第五天,今天股市雄起了,涨到了6,和之前的最合适买入0差了6,比之前的最大利润要大,所以在这天买入是血赚的,这是最大利润改为6,
- 第六天,今天继续割韭菜,跌倒了4, 和之前最适合买入差了4,没有之前的最大利润大,所以姚卖也是之前卖
走完了6天,知道了最大利润是6,这波是血赚的......
上面的大白话其实已经蕴含着这题的算法精髓了,精髓就是马后炮,每天都和前面股市最低的减一下,看能不能比前面赚的最多的还要多,是的话就替换掉......
fun maxProfit(prices: IntArray): Int {
if(prices.isEmpty() || prices.size == 1)
return 0
var maxProfit = 0
var nowLowest = prices[0]
for(i in 1 until prices.size){
if(prices[i] > nowLowest)
maxProfit = max(maxProfit,prices[i] - nowLowest)
else if(prices[i] < nowLowest)
nowLowest = prices[i]
}
return maxProfit
}
网友评论