leetCode 121 股票买卖最佳时机

题目描述：

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

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

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

示例输入输出：

  1. 输入：[7,1,5,3,6,4]
  2. 输出：5
  3. 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  4.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
  6. 输入：prices = [7,6,4,3,1]
  7. 输出：0
  8. 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

思路：

一次遍历

  • 记住最低点，然后每遍历到一个新的点位比较到目前最大差值与当前差值，记住最大差值。

  • 参数：

    • 最大差值maxPrice；当前最小值minPrice。

  • 终止条件：

    • 遍历到数组最后一个

  • 迭代过程中做的事：

    • 检查当前是否新的最小值

      • 是则重新定义最小值
      • 否则计算当前值与最小值差值

      • 判断是否大于最大差值

        • 更新最大差值

  • 复杂度分析：

    • 时间复杂度：只需要遍历一遍，O（n）
    • 空间复杂度：O（1）

  • 代码：

  • class Solution {
  public int maxProfit(int[] prices) {
      int maxPrice = Integer.MIN_VALUE;
      int minVal = prices[0];
      for(int i = 0; i < prices.length; i++){
          if(prices[i] < minVal){
              minVal = prices[i];
          }else if(maxPrice < prices[i] - minVal){
              maxPrice = prices[i] - minVal;
          }
      }
      return maxPrice;
  }
}