leetcode-29(买股票的最佳时机)

发布时间:2021-09-06 发表于话题:股票大于最大可买 点击:41 当前位置:财神股票资讯网 教育 leetcode-29(买股票的最佳时机) 手机阅读

题目:给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

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

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

解析:本题难度为简单。这道题说白了,也就是要找出给定数组中两个数字之间的最大差值(即,最大利润)。此外,第二个数字(卖出价格)必须大于第一个数字(买入价格)。再直白点就是,对于每组 i 和 j(其中 j > i)我们需要找出 max(prices[j] - prices[i])。提供以下一些思路。

思路一:暴力算法。题目理解完,直接想到暴力算法。使用两个变量 i 和 j ,它们分别表示买进这支股票和卖出这支股票,暴力求出它们在价格数组上可能出现的所有位置。写一个二重循环即可。

思路二:优化暴力算法。要求最大利润,自是买入的股价越低越好,卖出的股价越高越好。所以我们只要关心之前所看到的最低股价,于是在遍历的过程中,记录下之前看到的最低股价,这样就可以省去内层循环,从而达到优化的目的。我们可以维持两个变量——minVal 和 res,它们分别对应目前为止所得到的最低价格和最大利润(卖出价格与最低价格之间的最大差值)。

思路三:差分数组法。因为我们关注股票的变化,所以明天减去今天的差价在一定程度上是有研究价值的。我们使用数组 diff 表示差分数组。如何得到差分数组,如图1所示

图1  得到差分数组

通过以下的两个例子,如图2所示。我们不难发现:差分数组的连续子区间和的值,就正好是原始股价数组进行一次交易的差价(后 - 前)。因此,本题又可以被转化为在差分数组上,求“最大连续子序列的和”。

图2  差分数组的连续子区间的和

代码(运行通过):

思路一:暴力解决,如图3所示

图3  暴力解法

思路二:优化暴力解法,如图4所示

图4  优化暴力解法

思路三:差分数组法,如图5所示

图5  差分数组法

思路三这想法还是可以的,我是没想过这题还能这么理解,非常佩服想出这个解法的大佬。

非常感谢你能看到这里,如有疑问或是不满意的地方,欢迎评论指出

本文来源:https://www.thyysj.com/info/596226.html

标签组:[股票] [利润

热门话题

教育推荐文章

教育热门文章