求教amazon oa max Stock price的思路

如题~
地里经典的股票max Price题目（题目见图）
我的思路是sliding window+ maintain 一个has

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

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

值，检查map.size() == k？如果等于就update sum值

感谢感谢~~

感觉就是找出长度为k且没有重复数字的subarray，只不过要同时maintain一个kSum记录当前array的sum而已
edge case会不会是没有符合条件的subarray返回一个特定值？

1. def func(arr, k):
   
2.     left = -1
   
3.     numberMap = {}
   
4.     kSum = 0
   
5.     ans = -float('inf')
   
6.     for i, num in enumerate(arr):
   
7.         if num in numberMap and numberMap[num] > left:
   
8.             left = numberMap[num]
   
9.         numberMap[num] = i
   
10.         kSum += num
    
11.         if i - k >= 0
    
12.             kSum -= arr[i - k]
    
13.         if i - k >= left:
    
14.             ans = max(ans, kSum)
    
15.     return -1 if ans == -float('inf') else ans

复制代码

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

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

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

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

我用了slide window+ hashset, 也不确定对不对, 贴上来互相讨论吧

没有问题啊，O(N)理论上是最优解了

lyyc 发表于 2022-7-24 17:19
没有问题啊，O(N)理论上是最优解了

我也觉得是·……但是我看有人有一些hidden case过不了，所以很迷惑

匿名用户 发表于 2022-07-24 15:17:38
我也觉得是·……但是我看有人有一些hidden case过不了，所以很迷惑

那估计是他们写错了，不是时间复杂度的问题

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

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

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

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

wanlu2012 发表于 2022-7-25 12:00
感谢提供思路～ 所以 hashmap 是在做优化，让 sliding window 左边的窗口收缩的更快，而不是一步一步收缩 ...

Right. Otherwise, you'd get TLE.