Given an array prices where prices[i] is the price of the ith item in a shop, return the final prices after applying a discount. The discount for prices[i] is the first price to its right that is less than or equal to prices[i]. If there is no such price, the item gets no discount. Example: Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3] Explanation: 8 gets a discount of 4, 4 gets a discount of 2, 6 gets a discount of 2, and 2/3 get no discount. Pattern focus: Monotonic Decreasing Stack for Next Greater / Next Smaller style scanning.
prices = item prices
answer[i] = discounted price after subtracting the first price to the right that is <= prices[i]
Example 1:
Input:
prices = [8,4,6,2,3]
Output:
[4,2,4,2,3]
Explanation:
Use a monotonic stack to locate the first affordable discount on the right.
Example 2:
Input:
prices = [1,2,3,4,5]
Output:
[1,2,3,4,5]
Explanation:
No later price is small enough to create a discount.