121. 买卖股票的最佳时机｜刷题打卡

一、题目描述：

给定一个数组 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。

提示：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

二、思路分析：

刚接触这个题目，觉的还是挺简单的，借鉴选择排序，两个循环就可以搞定。嗯，没错，就是下文方法一。

思路一：

既然给出一个数组求最大利润，那就先设定一个变量profit保存利润值。买入时间必须要比卖出时间早，并且盈利：卖出值 - 买入值 = 利润。在数组循环中寻求最大利润值。那就需要两个循环，用后面的股票值减去之前买入的，与保存的profit相比较，比profit大则更新profit值。

写完验证结果发现：超时！！

思路二：

超时肯定是，数据过多，导致超时。那就考虑能不能只用一个循环来解决。

在一个循环里，我至少要取到何时卖出值最大，何时买入值最小，并且买入值必须在卖出之前。

那么，拿到数组第一个值，可以将它定义为买入值min，在循环时，遇到比min小的就替换min。用每天的股价减去 当天之前最小值min 和利润值profit相比，如果prices[i] - min大于利润值，就替换profit。

这样就可以获取到利润的最大值了。 （我的理解和官方有点不同，我认为是循环时，取数组开始到当天的最小值，并不是数组中的最小值）。

三、AC 代码：

方法一：

function maxProfit(prices: number[]): number {
  let profit: number = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[j] - prices[i] > profit) {
        profit = prices[j] - prices[i];
      }
    }
  }
  return profit;
}

方法二：

function maxProfit(prices: number[]): number {
    let profit: number = 0;
    let min: number = prices[0]; // 买入
    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i];
        }
        if (prices[i] - min > profit) {
            profit = prices[i] - min;
        }
    }
    return profit;
};

四、总结：

解题时需要考虑性能，优化等方面！！

查看letcode官方解答后，发现此题确实存在争议。代码是对的，但是思路解释有点不同。

题目来源：leetcode。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情。

作者：ClyingDeng

链接：https://juejin.cn/post/6934666174597136392

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。