121. 买卖股票的最佳时机

难度: 简单

来源: 面试经典150题

---

给定一个数组 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 <= 105
• 0 <= prices[i] <= 104

class Solution {
    public int maxProfit(int[] prices) {

    }
}

分析与题解

---

• 枚举

  这个题目整体比较简单, 因为只有一次的买进卖出机会. 不需要动态规划. 直接枚举即可.

  我们都知道 低价买进高价卖出 会获利最高.

  所以我们需要遍历所有天的情况, 在这一天尝试卖出, 并在此天之前的最低的某一天买入. 然后依次比较.

  result = Math.max(result, prices[i] - minIn);
  minIn = Math.min(prices[i], minIn);
  

  整体逻辑代码如下所示.

  class Solution {
      public int maxProfit(int[] prices) {
          // 买卖股票问题
          // 按照题意我们只能进行一次买入卖出操作.
          // 实际上 我们考虑获得的最大利润 ,我们只需要低价买入 高价卖出即可.
          // 也就是说当天尝试卖出, 我们在之前最低点买入, 所以之前的最低点需要做记录
          int minIn = Integer.MAX_VALUE;
          int result = 0;
          for(int i = 0; i < prices.length; i++) {
              result = Math.max(result, prices[i] - minIn);
              minIn = Math.min(prices[i], minIn);
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 一次遍历循环, 时间复杂度与数组长度相关.
  • 空间复杂度: O(1), 常量级别的空间复杂度.

  结果如下所示.