Final Prices With a Special Discount in a Shop

lcpy gen -n 1475   # by problem number
lcpy gen -s final_prices_with_a_special_discount_in_a_shop   # by problem name

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation:
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.

Input: prices = [10,1,1,6]
Output: [9,0,1,6]

class Solution:
    # Time: O(n) - each index is pushed and popped at most once
    # Space: O(n) - for the index stack
    def final_prices(self, prices: list[int]) -> list[int]:
        answer = list(prices)
        stack: list[int] = []
        for i, price in enumerate(prices):
            while stack and prices[stack[-1]] >= price:
                answer[stack.pop()] -= price
            stack.append(i)
        return answer