055 · Final Prices With a Special Discount in a Shop
algorithm
Problem
给定一个整数数组 prices，其中 prices[i] 表示第 i 件商品的原价。
商店有一个特殊折扣规则：
对每件商品 i，从它右边的商品里找到第一个价格小于或等于 prices[i] 的商品 j。
如果找到了这样的商品，那么第 i 件商品的最终价格是：
prices[i] - prices[j]如果右边没有价格小于或等于它的商品，那么第 i 件商品没有折扣，最终价格仍然是 prices[i]。
请返回每件商品应用折扣后的最终价格数组。
例如：
prices = [8, 4, 6, 2, 3]对每个位置来看：
8右边第一个小于或等于它的是4，最终价格是8 - 4 = 44右边第一个小于或等于它的是2，最终价格是4 - 2 = 26右边第一个小于或等于它的是2，最终价格是6 - 2 = 42右边没有小于或等于它的价格，所以仍然是23右边没有商品，所以仍然是3
所以返回：
[4, 2, 4, 2, 3]Examples
示例 1
Input: prices = [8, 4, 6, 2, 3]
Output: [4, 2, 4, 2, 3]解释：8 的折扣是 4，4 和 6 的折扣都是 2，最后两个商品没有折扣。
示例 2
Input: prices = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]解释：每件商品右边都没有小于或等于自己的价格，所以所有价格都不变。
示例 3
Input: prices = [10, 1, 1, 6]
Output: [9, 0, 1, 6]解释：10 的折扣是右边第一个 1；第一个 1 的折扣是右边第二个 1；后两个商品没有折扣。
Constraints
- \(1 \leq\)
prices.length\(\leq 500\) - \(1 \leq\)
prices[i]\(\leq 1000\)
Link
→ Solution