1475. Final Prices With a Special Discount in a Shop
Description
You are given an integer array 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.
Example 1:
Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3] Explanation: For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. For items 3 and 4 you will not receive any discount at all.
Example 2:
Input: prices = [1,2,3,4,5] Output: [1,2,3,4,5] Explanation: In this case, for all items, you will not receive any discount at all.
Example 3:
Input: prices = [10,1,1,6] Output: [9,0,1,6]
Constraints:
1 <= prices.length <= 500
1 <= prices[i] <= 1000
Solutions
Solution 1: Monotonic Stack
The problem is essentially to find the first element on the right side that is smaller than each element. We can use a monotonic stack to solve this.
We traverse the array $\textit{prices}$ in reverse order, using the monotonic stack to find the nearest smaller element on the left side of the current element, and then calculate the discount.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{prices}$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|