Given the array
prices[i]is the price of the
ithitem in a shop. There is a special discount for items in the shop, if you buy the
ithitem, then you will receive a discount equivalent to
jis the minimum index such that
j > iand
prices[j] <= prices[i], otherwise, you will not receive any discount at all. Return an array where the
ithelement is the final price you will pay for the
ithitem of the shop considering the special discount. Examples: Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3] Input: prices = [1,2,3,4,5] Output: [1,2,3,4,5]
This question first appeared in the Leetcode Biweekly Contest 28, and the brute force approach is straightforward enough to come up with. However, inspired by @lee215, it could be also solved with the monotone stack, which amazingly reduces O(n^2) to O(n).
Brute force approach – O(n^2)
It uses a nested for-loop to check that, for each item, whether there is a coming number that is smaller or equal to it.
def finalPrices(self, prices: List[int]) -> List[int]: n = len(prices) for i in range(n): for j in range(i+1,n): if prices[j] <= prices[i]: prices[i] -= prices[j] break return prices
Monotone stack – O(n)
A monotone stack refers to a stack structure where numbers in it are increasing only or decreasing only. With a monotone stack, given a number, we can find the first item that is smaller or larger than it. More importantly, it achieves O(n) time complexity.
Here we implements an increasing monotone stack, and when we find one smaller item (than the last item in the stack), we would pop all larger items before pushing it into the stack.
def finalPrices(self, prices: List[int]) -> List[int]: stack =  for i,val in enumerate(prices): while stack and prices[stack[-1]] >= val: prices[stack.pop()] -= val stack.append(i) return prices