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

一、题目描述

二、思路分析：

分析题目：求数组中两个值之前的最大差值，限制差值必须是后一个位置减去前一个位置，如果小于 0，则返回 0，按照这个思路，直接就进入暴力循环，通过两层循环，实现实现对所有的差值进行比较。

var maxProfit = function (prices) {
  let max = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const diff = prices[j] - prices[i];
      // 错误记录：第一次忘了写 max，不是一次通过
      max = Math.max(max, diff);
    }
  }

  return max;
};

存在问题：当数组长度过长，报错：运行超出时间限制

时间复杂度：O(n^2);

空间复杂度：O(1), 只使用了常数个变量。

换一个思路理解，如果我们在第i天需要获得最大的利润，那么一定是减去在之前[0, i-1]个元素中的最低价格从而得到最大的利润。

var maxProfit = function (prices) {
  let minPrice = Infinity;
  let maxProfit = 0;
  for (let i = 0; i < prices.length; i++) {
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    } else if (maxProfit <  prices[i] - minPrice) {
      maxProfit =  prices[i] - minPrice
    }
  }

  return maxProfit;
};

时间复杂度：一次循环，O(n);

空间复杂度：O(1)，只使用了常数个变量。

三、总结：

本题的关键是思考的方向，在做算法题的时候多换几个方向思考，不用一言不合就上暴力，感觉当你进入暴力之后，思维就会逐渐固化，往这个方向去想，很难想到更好的方法了。而是应该在最开始的时候分析题目是什么类型，然后按照类型进行思考划分，是否能够这样解决。

本题是股票系列里面最简单的一道题，本次学习计划先把股票系列问题解决掉。加油！