Given the 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 theminimumindex such that`j > i`

and`prices[j] <= prices[i]`

, otherwise, you will not receive any discount at all.Return an array where theExamples:`ith`

element is the final price you will pay for the`ith`

item of the shop considering the special discount.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
```