1. 题目
  2. 解题思路

121 Best Time to Buy and Sell Stock

leetcode

题目

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

1
2
3
4
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

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

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

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

解题思路

1 暴力遍历, 复杂度 O(n2)O(n^2).
遍历 i (买入价格),用其后的所有 [i + 1,..., end] (卖出价格) 减去 i 算出对应的利润值, 从而找出最大的利润值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function maxProfit(prices) {
  let maxProfit = 0;
  let pricesLen = prices.length;

  for (let i = 0; i < pricesLen; i++) {
    // 买入价格
    const buyPrice = prices[i];
    for (let j = i + 1; j < pricesLen; j++) {
      // 卖出价格
      const sellPrice = prices[j];
      // 比较最大利润值
      maxProfit = Math.max(maxProfit, sellPrice - buyPrice);
    }
  }
  return maxProfit;
}

2 动态规划, 复杂度 O(n)O(n).
前 i 天的最大利润为: max( 前 i - 1 天的最大利润 , 第 i 天的最大利润 )
而第 i 天的最大利润为: 当天价格 - 前 i - 1 天的最小价格
需注意第一天的最大利润为 0, 最小价格为当天价格.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function maxProfit(prices) {
  let profits = [0];
  // 前 i - 1 天的最小价格
  let minPrice = prices[0];
  // 从第二天开始计算
  for (let i = 1; i < prices.length; i++) {
    // 第 i 天的价格
    const price = prices[i]
    // 前 i 天的最小价格
    // 当天的价格可能比前 i - 1 天都小
    minPrice = Math.min(minPrice, price);
    // 前第 i 的最大利润: max(前 i - 1 天的最大利润, 当天的最大利润)
    profits[i] = Math.max(profits[i - 1], price - minPrice);
  }
  return profits[profits.length - 1];
};

进一步优化.没必要保存所有的前 i 天最大利润, 单独存一个最大利润即可.

1
2
3
4
5
6
7
8
9
10
11
function maxProfit(prices) {
  // 最大利润
  let maxProfit = 0;
  let minPrice = prices[0];
  for (let i = 1; i < prices.length; i++) {
    const price = prices[i]
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }
  return maxProfit;
};