Amazon OA 向右看的数组题

题目在这里：
For example, assume there are items priced [2, 3, 1, 2, 4, 2].
The first and seco

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ost is 1+2+1+0+2+2 = 8 units.

应该要求O(n) 或者O(nlogn)
如果对于每个数都向右遍历一遍数组的话就是O(n^2), 不符合要求。

和这题一样，https://leetcode.com/discuss/int ... al-Discounted-Price
用stack做

楼主你这个是新题吗，看地里之前的面经好像都没有这道题

用一个升序的stack，右边有小于stack最后一个的，stack.pop 然后减去这个数字。

题目意思没看懂。。。

这个题不是我考到的 但是amazon OA的题确实是网上都有，这是我写的代码：

1. 
   
2.     def onSale(self, A):
   
3.         stack = []
   
4.         res = 0
   
5.         for i, a in enumerate(A):
   
6.             while stack and stack[-1][1] >= a:
   
7.                 top = stack.pop()[1]
   
8.                 res += top - a
   
9.             stack.append((i, a))
   
10. 
    
11.         res += sum([s[1] for s in stack])
    
12.         return res, [s[0] for s in stack]
    
13. 
    
14. print(onSale([2, 3, 1, 2, 4, 2]),
    
15.       onSale([5, 1, 3, 4, 6, 2]),
    
16.       onSale([1, 3, 3, 2, 5]),
    
17.       )

复制代码