有趣的算法『买卖股票的最佳时机』

2,369 阅读8分钟

买卖股票的最佳时机系列问题

买卖股票的最佳时机 I

给定一个数组,它的第  i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

示例 1:

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

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

来源:力扣(LeetCode)链接

思路

这个问题的难度是简单,记录一个最低价格,然后和每天的价格做差求最大利润就行了。

var maxProfit = function (prices) {
  let max = 0;
  let minPrice = prices[0];
  for (let i = 1; i < prices.length; i++) {
    minPrice = Math.min(minPrice, prices[i]);
    let currentMax = prices[i] - minPrice;
    max = Math.max(max, currentMax);
  }
  return max;
};

结果:

  • 200/200 cases passed (104 ms)
  • Your runtime beats 29.94 % of javascript submissions
  • Your memory usage beats 80.6 % of javascript submissions (38.2 MB)

买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:

1 <= prices.length <= 3 \* 10 ^ 4
0 <= prices[i] <= 10 ^ 4

思路

这道题也是简单题,比上一个要稍复杂一点,可以进行无数次的买卖。

思路就是记录动态最低价,然后碰到有利润的价格后,累积利润,然后切换最低价。

比如:[1,2,3,4,5],最低价刚开始为 1

  1. 最低价 1 和第二天价格 2 比较,发现了利润 1,利润和为 1,此时需要将最低价转换成 2,因为后续只有高于 2 的才可以获取更大的利润
  2. 最低价 2 和第三天价格 3 比较,发现了利润 1,利润和为 2,此时需要将最低价转换成 3
  3. 最低价 3 和第四天价格 4 比较,发现了利润 1,利润和为 3,此时需要将最低价转换成 4
  4. 最低价 4 和第五天价格 5 比较,发现了利润 1,利润和为 4,此时需要将最低价转换成 5
var maxProfit = function (prices) {
  // 利润累积的和
  let sum = 0;
  // 当前的最低价格
  let min = prices[0];
  for (let i = 1; i < prices.length; i++) {
    // 如果现在价格高于当前的最低价,就累积利润
    if (prices[i] > min) {
      sum += prices[i] - min;
      // 累积了之后,需要切换下最低价
      min = prices[i];
    } else {
      // 当前价格等于或者低于最低价的时候需要切换
      min = prices[i];
    }
  }
  return sum;
};

仔细看上面的代码,最后优化下:

var maxProfit = function (prices) {
  // 利润累积的和
  let sum = 0;
  // 当前的最低价格
  let min = prices[0];
  for (let i = 1; i < prices.length; i++) {
    // 如果现在价格高于当前最低价,就累积利润
    if (prices[i] > min) {
      sum += prices[i] - min;
    }
    // 当前价格高于、等于或者低于最低价的时候需要切换
    min = prices[i];
  }
  return sum;
};

结果:

  • 200/200 cases passed (92 ms)
  • Your runtime beats 27.45 % of javascript submissions
  • Your memory usage beats 83.16 % of javascript submissions (38.2 MB)

买卖股票的最佳时机 III

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
     随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

思路

这道题的难度是 hard,不是很好解决。

如果说最大允许一次交易,那么大多数人都知道怎么解决。下面让我们把这道题转化成『最大允许一次交易』

『当前卖出的最大利润』=『这次卖出的价格』-『买入的最低价格』

继续变形:

『当前卖出的最大利润』=『这次卖出的价格』-『买入的综合最低价格』

什么是『买入的综合最低价格』呢?就是(『买入价格』-『上一次的买卖利润最大值)的最小值

所以我们需要求出一个综合的最小值,上代码感受下

var maxProfit = function (prices) {
  let min1 = prices[0];
  let min2 = prices[0];
  let max1 = 0;
  let max2 = 0;
  for (let index = 1; index < prices.length; index++) {
    // 当前遇到的最低价
    min1 = Math.min(min1, prices[index]);
    // 当前为止,第一次交易赚的钱的最大值
    max1 = Math.max(max1, prices[index] - min1);
    // 当前买入的综合最低价(计算了上一个交易的利润)
    min2 = Math.min(min2, prices[index] - max1);
    // 当前卖出的最高利润
    max2 = Math.max(max2, prices[index] - min2);
  }
  return max2;
};

结果:

  • 200/200 cases passed (80 ms)
  • Your runtime beats 81.89 % of javascript submissions
  • Your memory usage beats 93.41 % of javascript submissions (38.3 MB)

有趣的算法『打开转盘锁』

有趣的算法『爬楼梯』