关于算法:力扣之买卖股票的最佳时机

44次阅读

共计 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) // 而后求出这个数组中的最大值即为最大收益
}

正文完
 0