题目
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
1
2
3
4
5 输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。示例 2:
1
2
3 输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
首先是具体场景中的思路:如何求得最高利润?假设我当前买入的是历史最低价股票,看看我最多能赚多少,也就是找到从今天以后最高的股票价格。
单调栈解法
把股票问题抽象出来:求某个数与其右侧最大数的差值。
以下为参考精选题解的思路:
当你需要高效查询某个位置左右两侧比它大(或小)的数的位置时,可以使用单调栈。
自己的理解:如何翻译使用单调栈的思路?
就像之前做过的每日天气,需要找到所有温度上升的阶段,这道题也是一样,需要找到给定数组的上升区间,这时候我们使用单调递增栈,维护栈的从栈底到栈顶单调递增的特性,也就是说当前值大于栈顶,则入栈,否则,代表当前曲线开始下降,为了维护栈的单增特性,需要将栈中大于当前值的元素全部弹栈,再将当前元素入栈。
这样维护一个单调栈,我们最终可以得到曲线的总体趋势:对于这道题来讲,如果从第一天到最后一天,股票整体是涨了还是跌了。在维护单调栈的过程中,每一次出栈操作都意味着曲线在下降,也就是说遇到了一个局部最大值,此时必然是最优解的一个可能解,所以每次出栈时,同时要计算此时抛售股票的利润,并且更新全局最大值。
注意:
- 我们只在出栈时求解并更新利润最大值,这会带来一个问题,股票价格一路上涨从不下跌时,我们没有更新价格,所以一个需要在循环外处理的点是循环结束时(遍历完整个数组),求最终利润并更新利润。
代码:
1 | class Solution { |
- 时间复杂度$O(N)$
- 空间复杂度$O(N)$
动态规划解法
根据官方的“一次遍历”解法,总结其思路:
我们希望自己的股票是用历史最低价买入的,那么到第$i$天,我们都假设我们的股票的买入时间是在前$i$天的最低价那天买入的,那我们思考的问题就变成,我们今天要不要抛出去?优化目标是利润最大化,那么我今天是否选择抛售取决于抛售与不抛售对当前利润的影响,我们取利润最大的作为新的全局最大值,当然这里只是假设我们卖了,不会影响第二天的计算。
1 | class Solution { |
动态规划的其他思路
- 把利润看成涨幅与跌幅的累加,那么问题就变成了原序列求差序列(求导)的最大子序和。
- 通用解法,列出该问题中所有需要用到的状态,找出状态转移关系式。
总结
这道题最大的总结其实是单调栈解法,如果一个问题让我们想到需要找出上升阶段或下降阶段,那么我们可以考虑单调栈。