共计 2578 个字符,预计需要花费 7 分钟才能阅读完成。
题目形容
给定一个数组 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。
力扣原题目地址:https://leetcode.cn/problems/…
思路剖析
对于这道题目,能够两次循环暴力求后果,不过不太好,此处不说暴力求解后果的代码形式(附在最初)
。
咱们个别遇到一个简单问题的时候,能够 把简单问题进行简化拆解
,在解决简化拆解问题的时候,寻找法则、发现法则,最终 在简单问题上应用咱们之前发现的简化问题类似的法则
,从而解决之
比方老板上来就让咱们制作一个原子弹,啊,不会啊。没关系咱们先钻研一下,如何制作一个手榴弹。反正都是蛋嘛,都是爆炸用的,总是有相通之处,手榴弹制作进去了,原子弹也就快了。这个比喻不太失当,反正是那个意思,大家自行领会哈
^_^
浏览题目当前咱们大略晓得需要如下:
-
要想取得最高收益,就必须在低位买进、高位卖出
- 即:
找到数组中的最大值,最小值,最大减最小就是最高收益
- 即:
-
股票是,先买后卖。所以买股票的工夫靠前、卖股票的工夫靠后
- 即:
最小值的地位索引要小于最大值的地位索引
- 即:
- 问题是,咱们临时不晓得那天买进股票最低,那天最高???
罗唆,咱们就假如,头一天股票最低,3 块钱就能买,前面股票涨涨跌跌,然而,始终没有低于 3 块的。所以头一天买进最划算。咱们以 5 天为周期,刷卡付款头一天买了。于是就模仿定义一个数组:let arr = [3,8,6,12,9]
,接下来,咱们把问题转化成:
已知第一天买的股价最低,前面的每一天都比第一天股价高,求那一天卖掉最多能赚多少钱
简单问题拆解之简化
于是咱们依据需要,能够写出上面的代码:
let arr = [3, 8, 6, 12, 9]
function maxProfit(prices) {
// 1. 假如初始收益为 0,前面每一天的价格减去第一天的买入价格就是收益
let maxProfitValue = 0
for (let i = 1; i < prices.length; i++) {
// 2. 只有收益大的(收益大的记在本子上,收益小的划掉不要)maxProfitValue = Math.max(maxProfitValue, prices[i] - 3)
}
// 3. 最终失去一个最大收益,并返回
return maxProfitValue;
}
console.log(maxProfit(arr) ); // 9
上述代码 maxProfitValue = Math.max(maxProfitValue, prices[i] - 3)
咱们能够换一下写法,因为 3
是第一天的价格,所以换成arr[0]
即:
简单问题拆解之简略变换
let arr = [3, 8, 6, 12, 9]
function maxProfit(prices) {let min = prices[0] // 变换之~ 咱们已知最低点股价是第一项,故定义变量示意
// 1. 假如初始收益为 0,前面每一天的价格减去第一天的买入价格就是收益
let maxProfitValue = 0
for (let i = 1; i < prices.length; i++) {
// 2. 只有收益大的(收益大的记在本子上,收益小的划掉不要)maxProfitValue = Math.max(maxProfitValue, prices[i] - min) // 变换之~ 最低价是 min,这里卖出高价 - 买入最低价也是用 min 变量了
}
// 3. 最终失去一个最大收益,并返回
return maxProfitValue;
}
console.log(maxProfit(arr) ); // 9
看到这里,有的敌人说了,如果第一天、数组中的第一项不是最小的呢?如果第二项有可能比第一项小呢?没关系,咱们比照一下就行了,谁小用谁。反正有循环,能够拿到每一项的值,比照就是喽。伪代码如下:
let min = arr[0] // 假如第一项最小
min = Math.min(min,arr[i]) // 第二项和当下最小值做比照,谁小就保留谁
Math.min(5,2,8,3) // Math.min 求一组数中的最小值 左侧代码执行失去后果 2
于是上述代码又能够做一个变换
简单问题之变换解决之
function maxProfit(prices) {let min = prices[0] // 1. 假如最低股价是第一项,若后续有更低的股价,就用后续更低的
let maxProfitValue = 0 // 2. 假如初始收益为 0,前面每一天的价格减去买入价格就是收益
for (let i = 1; i < prices.length; i++) {min = Math.min(min, prices[i]) // 3. 变换解决之,应用 Math.min 比照一下,看那一天的股价最低,就用那个
// 4. 只有收益大的(收益大的记在本子上,收益小的划掉不要)maxProfitValue = Math.max(maxProfitValue, prices[i] - min) // 5. 已知最低价是 min,那么收益就等于卖出价 - 最低价
}
return maxProfitValue; // 6. 最终失去一个最大收益,并返回
}
好了,看到这里,力扣算法题也就解决啦。所以思路很重要:简单的问题简单化,在简单化解决的过程中一直寻找法则,从而向复杂化过渡,最终通过寻得的法则解决复杂化的问题
附:双层循环暴力解法
function maxProfit(prices) {let arr = [0] // 指定默认收益为 0
for (let i = 0; i < prices.length; i++) {for (let j = i + 1; j < prices.length; j++) {arr.push(prices[j] - prices[i]) // 把所有计算出的利润都追加到一个数组中
}
}
return Math.max(...arr) // 而后求出这个数组中的最大值即为最大收益
}