題目描述：

給你一個數組 prices ，其中 prices[i] 是商店里第 i 件商品的價格。

商店里正在進行促銷活動，如果你要買第 i 件商品，那么你可以得到與 prices[j] 相等的折扣，其中 j 是滿足 j > i 且 prices[j] <= prices[i] 的 最小下標 ，如果沒有滿足條件的 j ，你將沒有任何折扣。

請你返回一個數組，數組中第 i 個元素是折扣后你購買商品 i 最終需要支付的價格。

示例 1：
輸入：prices = [8,4,6,2,3]
輸出：[4,2,4,2,3]
解釋：
商品 0 的價格為 price[0]=8 ，你將得到 prices[1]=4 的折扣，所以最終價格為 8 - 4 = 4 。
商品 1 的價格為 price[1]=4 ，你將得到 prices[3]=2 的折扣，所以最終價格為 4 - 2 = 2 。
商品 2 的價格為 price[2]=6 ，你將得到 prices[3]=2 的折扣，所以最終價格為 6 - 2 = 4 。
商品 3 和 4 都沒有折扣。

示例 2：
輸入：prices = [1,2,3,4,5]
輸出：[1,2,3,4,5]
解釋：在這個例子中，所有商品都沒有折扣。

示例 3：
輸入：prices = [10,1,1,6]
輸出：[9,0,1,6]

提示：
1 <= prices.length <= 500
1 <= prices[i] <= 10^3

解題思路一：暴力解法。兩層for。

class Solution:def finalPrices(self, prices: List[int]) -> List[int]:ans = []n = len(prices)for i in range(n-1):flag = 1for j in range(i+1,n,1):if prices[i] >= prices[j]:ans.append(prices[i] - prices[j])flag = 0breakif flag: ans.append(prices[i])ans.append(prices[n-1])return ans

時間復雜度：O(n²)
空間復雜度：O(1)

解題思路二：單調棧，具體思路是反向遍歷數組prices。遇到棧頂元素小于當前元素的就出棧，目的是為了找到當前位置右邊的第一個小于等于的元素即為棧頂元素。此時我們可以直接遍歷一遍得到答案。妙蛙！ 😃 😃 😃

可以參考LeetCode-496. 下一個更大元素 I【棧 數組 哈希表 單調棧】

class Solution:def finalPrices(self, prices: List[int]) -> List[int]:n = len(prices)res = [0] * nstack = []for i in reversed(range(n)):while stack and prices[i] < stack[-1]: stack.pop()res[i] = prices[i] - stack[-1] if stack else prices[i]stack.append(prices[i])return res

時間復雜度：O(n)
空間復雜度：O(n)棧空間

解題思路三：0