121.买卖股票的最佳时机.md

121.买卖股票的最佳时机

/*
 * @lc app=leetcode.cn id=121 lang=typescript
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
function maxProfit(prices: number[]): number {}
// @lc code=end

解法 1: 动态规划

function maxProfit(prices: number[]): number {
  let [min, res] = [prices[0], 0]
  for (const price of prices) {
    res = Math.max(res, price - min)
    min = Math.min(min, price)
  }
  return res
}

解法 2: 单调递增栈

function maxProfit(prices: number[]): number {
  let [stack, max, n] = [[prices[0]], 0, prices.length]
  for (let i = 1; i <= n; i++) {
    while (stack.length && (prices[i] < stack[stack.length - 1] || i === n)) {
      max = Math.max(max, stack[stack.length - 1] - stack[0])
      stack.pop()
    }
    stack.push(prices[i])
  }
  return max
}

Case

test.each([
  { input: { prices: [7, 1, 5, 3, 6, 4] }, output: 5 },
  { input: { prices: [7, 6, 4, 3, 1] }, output: 0 },
  { input: { prices: [1, 2] }, output: 1 },
])(`input: prices = $input.prices`, ({ input: { prices }, output }) => {
  expect(maxProfit(prices)).toBe(output)
})