1475.商品折扣后的最终价格.md

1475.商品折扣后的最终价格

/*
 * @lc app=leetcode.cn id=1475 lang=typescript
 *
 * [1475] 商品折扣后的最终价格
 */

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

解法 1: 单调栈

function finalPrices(prices: number[]): number[] {
  const n = prices.length
  let res: number[] = [],
    stack: number[] = []
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length && prices[i] < stack[stack.length - 1]) stack.pop()
    if (stack.length) {
      res[i] = prices[i] - stack[stack.length - 1]
    } else {
      res[i] = prices[i]
    }

    stack.push(prices[i])
  }
  return res
}

Case

test.each([
  { input: { prices: [8, 4, 6, 2, 3] }, output: [4, 2, 4, 2, 3] },
  { input: { prices: [1, 2, 3, 4, 5] }, output: [1, 2, 3, 4, 5] },
  { input: { prices: [10, 1, 1, 6] }, output: [9, 0, 1, 6] },
])('input: prices = $input.prices', ({ input: { prices }, output }) => {
  expect(finalPrices(prices)).toEqual(output)
})