Compute final prices with next smaller discount

You are given an integer array prices of length n, where prices[i] is the original price of the i-th item.

For each item i, find the first index j > i such that prices[j] <= prices[i]. That prices[j] becomes the discount for item i, so the final price of item i is:

• prices[i] - prices[j] if such j exists
• otherwise prices[i]

Return an array finalPrices of length n containing the final price for each item.

Input

• prices: array of integers

Output

• finalPrices: array of integers

Example

• Input: prices = [8, 4, 6, 2, 3]
• Output: [4, 2, 4, 2, 3]

Constraints (typical)

• 1 <= n <= 2e5
• 1 <= prices[i] <= 1e9

Compute Final Prices with Next Smaller Discount

Hints

1. A brute-force search for each item would be too slow for large inputs. Think about how to remember items that are still waiting for a discount.
2. Use a monotonic stack of indices. When the current price is less than or equal to the price at the top index, it can serve as that item's discount.