# 1475. Final Prices With a Special Discount in a Shop """ you are given an integer array 'prices' where 'prices[i]' is the price of the i'th item in a shop. there is a special discount for items in the shop. if you buy the i'th item, then you will receive a discount equivalent to 'prices[j]' where 'j' is the minimum index such that 'j > i' and 'prices[j] <= prices[i]'. otherwise, you will not receive any discount at all. return an integer array 'answer' where 'answer[i]' is the final price you will pay for the i'th item of the shop, considering the special discount """ class Solution(object): def finalPrices(self, prices): """ :type prices: List[int] :rtype: List[int] """ stack = [] for i, j in enumerate(prices): while stack and prices[stack[-1]] >= j: prices[stack.pop()] -= j stack.append(i) return prices if __name__ == "__main__": obj = Solution() print(obj.finalPrices(prices=[8, 4, 6, 2, 3])) print(obj.finalPrices(prices=[1, 2, 3, 4, 5])) print(obj.finalPrices(prices=[10, 1, 1, 6]))