Final Prices With a Special Discount in a Shop
EasyProblem Statement
prices where prices[i] is the price of the ith item in a shop.
There is a special discount for items in the shop. If you buy the ith 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 ith item of the shop, considering the special discount.Examples
prices = [8,4,6,2,3][4,2,4,2,3]• For item 0 with price[0] = 8, the first smaller or equal item to the right is prices[1] = 4. Final price = 8 - 4 = 4. • For item 1 with price[1] = 4, the first smaller or equal item to the right is prices[3] = 2. Final price = 4 - 2 = 2. • For item 2 with price[2] = 6, the first smaller or equal item to the right is prices[3] = 2. Final price = 6 - 2 = 4. • For item 3 with price[3] = 2, there is no item to the right with price <= 2. Final price = 2. • For item 4 with price[4] = 3, there is no item to the right with price <= 3. Final price = 3.
prices = [1,2,3,4,5][1,2,3,4,5]In this case, for all items, there is no other item to the right with a smaller or equal price. Therefore, no discount is applied to any item.
prices = [10,1,1,6][9,0,1,6]• For item 0 with price[0] = 10, discount is prices[1] = 1. Final price = 10 - 1 = 9. • For item 1 with price[1] = 1, discount is prices[2] = 1. Final price = 1 - 1 = 0. • For item 2 with price[2] = 1, no smaller/equal element to the right. Final price = 1. • For item 3 with price[3] = 6, last element has no elements to its right. Final price = 6.
Constraints
1 <= prices.length <= 5001 <= prices[i] <= 1000