1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
# 1475. Final Prices With a Special Discount in a Shop
"""
you are given an integer array 'prices' where 'prices[i]' is the price of the
i'th item in a shop. there is a special discount for items in the shop. if
you buy the i'th 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 i'th item of the shop, considering the special discount
"""
class Solution(object):
def finalPrices(self, prices):
"""
:type prices: List[int]
:rtype: List[int]
"""
stack = []
for i, j in enumerate(prices):
while stack and prices[stack[-1]] >= j:
prices[stack.pop()] -= j
stack.append(i)
return prices
if __name__ == "__main__":
obj = Solution()
print(obj.finalPrices(prices=[8, 4, 6, 2, 3]))
print(obj.finalPrices(prices=[1, 2, 3, 4, 5]))
print(obj.finalPrices(prices=[10, 1, 1, 6]))
|