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

题目形容

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