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.
Example 1
Input
prices = [8,4,6,2,3]Output
[4,2,4,2,3]Item 0 gets discount 4, item 1 gets discount 2, item 2 gets discount 2, and items 3 and 4 receive no discount.
Example 2
Input
prices = [1,2,3,4,5]Output
[1,2,3,4,5]In this case, for all items, you will not receive any discount at all.
Constraints
- 1 <= prices.length <= 500
- 1 <= prices[i] <= 1000