【刷题第 2 天】买卖股票的最佳时机

一、题目描述：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例

输入：[7,1,5,3,6,4]输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

二、思路分析：

该题目作为买卖股票系列的第一题，相对比较简单，最开始刷题时刷过一次，这里记录一下刷该该题目的心路历程。

题目要求只能交易一次即买入一次，卖出一次，求解最大利润。

因此题目可以转化为找两天，这两天要满足下面两个条件:

• 卖出天价位大于买入天

• 卖出天要位于买入天之后

暴力法

这个题目最容易思考的方法就是暴力法，遍历数组，枚举所有的二元组情况，且枚举的二元组一定要满足上述两个条件，计算出最大的利润。

遍历枚举二元组，因此我们可以轻松的分析出时间复杂度为 O(n2)

动态规划

暴力法通常不会是最优的解，我们来进一步思考，动态规划大法好，遇到题目先想动规。

我们设定一个 dp 数组，索引 i 处代表 i 以前的最低价格(存储最低买入价位)；设立一个变量 maxPro 存储最大利润。

遍历数组，当我们遍历到 i 时:

• 若 prices[i] > dp[i] 则与当前最大利润比较，若大于最大利润，则更新；反之，不更改

• 若 prices[i] > dp[i] 则更新 dp[i] = prices[i]

继续循环，这样我们就一次遍历就可以求出最大利润。

上面的 dp[i] 没有多余的状态转移，因此我们可以通过一个简单变量 minPro 替换他。

三、AC 代码：

var maxProfit = function(prices) {    let maxPro = 0;    let nowMinPro = prices[0];    let d = prices.length;    if (d === 1) {        return maxPro;    }    for (let i = 1; i<d; i++) {        if (nowMinPro > prices[i]) {            nowMinPro = prices[i];        }else {            maxPro = Math.max(maxPro, prices[i] - nowMinPro);        }    }    return maxPro;};复制代码

四、总结：

坚持刷题第二天，芜湖，开心!!!