All problems

Final Prices With a Special Discount

Easy · monotonic-stack

A shop puts its items in a single row on a shelf. prices[i] is the price of the item at position i. Today every item comes with a coupon: when you buy the item at position i, you get a discount equal to the price of the first item to its right (at a position j > i) whose price is less than or equal to prices[i]. If no item to its right is that cheap, the item gets no discount.

Return a list where entry i is what you pay for the item at position i: its price minus its discount.

Examples

Example 1

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

Output: [4, 2, 4, 2, 3]

The 8 is discounted by the first later price that is at most 8, which is 4. The 4 is discounted by 2, and the 6 by 2. The 2 and the 3 have nothing cheap enough to their right, so they cost full price.

Example 2

Input: prices = [1, 2, 3, 4, 5]

Output: [1, 2, 3, 4, 5]

Prices only go up, so no item has a cheaper item to its right and nothing is discounted.

Example 3

Input: prices = [10, 1, 1, 1]

Output: [9, 0, 0, 1]

An item equal in price counts: the 1s discount each other, and the last 1 pays full price.

Constraints