求教amazon oa max Stock price的思路

PipEvangelist 发表于 2022-7-25 12:09
Right. Otherwise, you'd get TLE.

Thanks! Appreciate your help~

您好！
本帖隐藏的内容需要积分高于 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

Hhhlium 发表于 2022-7-25 21:15
这里直接初始把ans 设为 -1 是不是就可以不用在return的时候判断了

这个地方应该是没问题的，因为说了是stock market所以不应该出现负数。
但是把题目换一下或者强行解释可以出现负数的话，用负无穷最安全。

PipEvangelist 发表于 2022-7-25 12:09
Right. Otherwise, you'd get TLE.

Can you share the code? I would like to check whether my solution is correct. Thx~

这是我的解法，不知道能不能过所有的 test care，欢迎大家指正错误～

1. public int maxPrice(int[] prices, int k) {
   
2.             if (prices == null || prices.length == 0) {
   
3.                 return 0;
   
4.             }
   
5. 
   
6.             Set<Integer> window = new HashSet<>();
   
7.             Map<Integer, Integer> numToIdx = new HashMap<>();
   
8.             int maxPrice = 0;
   
9.             int left = 0, right = 0;
   
10.             int currSum = 0;
    
11. 
    
12.             while (right < prices.length) {
    
13.                 while (right < prices.length && window.size() < k) {
    
14.                     if (window.contains(prices[right])) {
    
15.                         // move to next non-duplicate position
    
16.                         int nextLeft = numToIdx.get(prices[right]) + 1;
    
17. 
    
18.                         while (left < nextLeft) {
    
19.                             window.remove(prices[left]);
    
20.                             numToIdx.remove(prices[left]);
    
21.                             currSum -= prices[left];
    
22.                             left++;
    
23.                         }
    
24. 
    
25.                     } else {
    
26.                         window.add(prices[right]);
    
27.                         currSum += prices[right];
    
28.                         numToIdx.put(prices[right], right);
    
29.                         right++;
    
30.                     }
    
31.                 }
    
32. 
    
33.                 maxPrice = Math.max(maxPrice, currSum);
    
34. 
    
35.                 window.remove(prices[left]);
    
36.                 currSum -= prices[left];
    
37.                 left++;
    
38.             }
    
39. 
    
40.             return maxPrice;
    
41. 
    
42.         }

复制代码

补充内容 (2022-07-26 15:54 +8:00):
不知道为啥缩进变得这么多，格式有点乱 QAQ

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

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

桃蹊 发表于 2022-7-28 15:56
while (left < nextLeft) 这里会infinity loop～你可以试试{1, 2, 3, 2, 4}和k = 3这个test case

谢谢建议～不过我 run 了一下好像 infinity loop，输出是 9

是不是错在这里？
long res = -1?
如果数组里全是负数（股价有没有可能是负数？），试试res = Integer.MIN_VALUE呢?

补充内容 (2022-07-30 17:35 +8:00):
哈哈，回太早了，没事了。。。

南宫狗剩 发表于 2022-07-24 18:53:52
碰到重复数字不能直接把curSum直接清0,也不能把left直接放到right那里，举个例子：
arr = , k = 3
当读到第二个2时，你把curSum清0，然后从2开始往后找，最后你算出来

谢谢指证🙏