亚麻10月社招OA新鲜面经~新人求米！！！

第二题我有点思路，抛砖引玉：
设两个priority queue，一个从小到大，一个从大到小，每读一个数就同时push进两个pq，内部遍历一遍。
时间复杂度n^2，空间n。

南宫狗剩 发表于 2021-10-3 19:28
第二题我有点思路，抛砖引玉：
设两个priority queue，一个从小到大，一个从大到小，每读一个数就同时push ...

没明白这个思路，能展开说说么？

我也考到了第二题，但是没做出来😭

感觉第二题像个数学题，比如每个subarray长为3的情况，3-1，4-2，5-3，6-4相加以后中间的3，4都抵消掉了

补充内容 (2021-10-04 14:29 +08:00):
不太对，好像还是需要mono stack

HayleyTGKX 发表于 2021-10-3 22:36
没明白这个思路，能展开说说么？

又想了一下，应该是两个priority stack，但是必须要允许随机访问才行，用个普通array就行了。

1. def solution( arr):
   
2.     minStack, maxStack = [], []
   
3.     ans = 0
   
4.     for index, num in enumerate( arr):
   
5.         while minStack and arr[ minStack[-1]] >= num:
   
6.             minStack.pop()
   
7.         while maxStack and arr[ maxStack[-1]] <= num:
   
8.             maxStack.pop()
   
9.         minStack.append( index)
   
10.         maxStack.append( index)
    
11.         i = j = 0
    
12.         pre = -1
    
13.         while arr[ minStack[i]] < arr[ maxStack[j]]:    #当且仅当i和j都到栈顶时结束
    
14.             ans += ( arr[ maxStack[j]] - arr[ minStack[j]]) * ( min( minStack[i], maxStack[j]) - pre)
    
15.             if minStack[i] < maxStack[j]:
    
16.                 pre = minStack[i]
    
17.                 i += 1
    
18.             else:
    
19.                 pre = maxStack[j]
    
20.                 j += 1
    
21.     return ans

复制代码

或许会有bug，懒得检查了，将就看吧。

南宫狗剩 发表于 2021-10-3 20:53
又想了一下，应该是两个priority stack，但是必须要允许随机访问才行，用个普通array就行了。或许会有bug ...

这么复杂，你是怎么想出来的？LC上有类似的题？

HayleyTGKX 发表于 2021-10-5 00:40
这么复杂，你是怎么想出来的？LC上有类似的题？

看LC-舅灵其

论坛匿名用户 发表于 2021-10-4 08:42
看LC-舅灵其

我OA前还做了这道题，可是仍然没有get到。啊天呐，我都要怀疑自己的智商了

HayleyTGKX 发表于 2021-10-5 02:16
我OA前还做了这道题，可是仍然没有get到。啊天呐，我都要怀疑自己的智商了

OA又不开摄像头，你为啥不手机搜搜呢。LC discussion 里也有这题。Anyway , 祝好运!

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

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