求问光大最后一题咋做 java爆堆空间 python tle 过了73% 求大佬指点下

说好的逻辑面 结果全是技术拷打哈哈哈哈 但还是很喜欢面试官风格很喜欢的公司求求了给我发offer更新下，10.10 在昨天收到喜欢的小红书博主离世的消息后，今天上午携程笔试还徘徊在难言的悲伤中，笔试中途接到一个电话，以为是hr，故提前终止笔试接电话，结果没接到，看了眼邮箱，看到了柠檬🍋发来的感谢信，有点失落，不仅是因为感谢信，更是在刹那间在迷宫中迷失了生命的方向。

凉凉 第一题 20% 超时 第二题 80% 超时 第三题 Floyd 直接炸内存第一题最后两分钟改了lazy update 的做法 但有bug 直接交了顺便一问 第一题是 lazy update 吗？用栈存当前 t 顺序，然后一个 set 存已经被 remove 掉的 然后在每次 t 更新的时候都 update 一下现在的栈 取里面最新的两个时间（如果有第三题是 Floyd 吗？感觉直接 Floyd 再处理出所有叶子 然后算当前节点到所有叶子的最小距离 但这么写直接爆内存 试了一下用稀疏表大小不能超过 10^4*10^4 而数据范围是10^5 不优化交结果直接爆内存 试着卡了一下范围 卡到 10^4 的大小，结果第一个用例直接 wa，看起来第一个用例就没想让我过（我也太菜了感觉阿里云不像想招人的样子

第一题是要用牛顿迭代才能AC🐴？二分只过了80%，还是我写错了😂P.S. 如果答题过程中，有人背景音聊天会算作弊吗？在实验室考的，学妹突然来了，俩学妹聊天，我在考试也不好说话😂如果真算作弊，那可能是阿里无缘吧！

在尝试用&nbsp;TreeSet&nbsp;实现，但是还是连着&nbsp;wa&nbsp;了两次，过了&nbsp;0&nbsp;个用例，心态有点爆炸，就提前&nbsp;5&nbsp;分钟交卷，结果尿了泡尿，好像检查出自己的问题在&nbsp;rightEdge&nbsp;和&nbsp;leftEdge&nbsp;没有和&nbsp;l，r&nbsp;取并集上，心态更炸裂，这次的题目感觉很简单，前两道题&nbsp;15&nbsp;分钟就做完了，第三题看着也不难，不知道大家都咋样？这道题我想的思路是用&nbsp;treeset&nbsp;保存所有&nbsp;max&nbsp;值的下标，然后判断&nbsp;l,r&nbsp;区间内有没有&nbsp;max&nbsp;值，有几个&nbsp;max&nbsp;值，l,&nbsp;r&nbsp;区间外有没有&nbsp;max&nbsp;值来实现import&nbsp;java.util.Scanner;import&nbsp;java.util.Arrays;import&nbsp;java.util.HashMap;import&nbsp;java.util.TreeSet;import&nbsp;java.util.HashSet;//&nbsp;注意类名必须为&nbsp;Main,&nbsp;不要有任何&nbsp;package&nbsp;xxx&nbsp;信息public&nbsp;class&nbsp;Main&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;void&nbsp;main(String[]&nbsp;args)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Scanner&nbsp;in&nbsp;=&nbsp;new&nbsp;Scanner(System.in);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;注意&nbsp;hasNext&nbsp;和&nbsp;hasNextLine&nbsp;的区别&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n&nbsp;=&nbsp;in.nextInt(),&nbsp;q&nbsp;=&nbsp;in.nextInt();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;arr&nbsp;=&nbsp;new&nbsp;int[n];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TreeSet&nbsp;set&nbsp;=&nbsp;new&nbsp;TreeSet<>();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;max_val&nbsp;=&nbsp;0;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr[i]&nbsp;=&nbsp;in.nextInt(); if (arr[i] >&nbsp;max_val)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max_val&nbsp;=&nbsp;arr[i];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;set.clear();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;set.add(i&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} while (q-- >&nbsp;0)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;l&nbsp;=&nbsp;in.nextInt();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;r&nbsp;=&nbsp;in.nextInt();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(l&nbsp;==&nbsp;1&nbsp;&amp;&amp;&nbsp;r&nbsp;==&nbsp;n)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(set.size()&nbsp;==&nbsp;1)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(&quot;lose&quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(r&nbsp;==&nbsp;l&nbsp;?&nbsp;2&nbsp;:&nbsp;r&nbsp;-&nbsp;l&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(&quot;draw&quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(r&nbsp;==&nbsp;l&nbsp;?&nbsp;2&nbsp;:&nbsp;r&nbsp;-&nbsp;l&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} if (set.ceiling(l) == null || set.floor(r) == null || set.ceiling(l) >&nbsp;r&nbsp;||&nbsp;set.floor(r)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(&quot;win&quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;right_edge&nbsp;=&nbsp;set.ceiling(l)&nbsp;==&nbsp;null&nbsp;?&nbsp;Integer.MAX_VALUE&nbsp;:&nbsp;set.ceiling(l);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;left_edge&nbsp;=&nbsp;set.floor(r)&nbsp;==&nbsp;null&nbsp;?&nbsp;Integer.MIN_VALUE&nbsp;:&nbsp;set.floor(r);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;min_size&nbsp;=&nbsp;Math.min(right_edge&nbsp;-&nbsp;l&nbsp;+&nbsp;1,&nbsp;r&nbsp;-&nbsp;left_edge&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(min_size&nbsp;==&nbsp;1&nbsp;?&nbsp;2&nbsp;:&nbsp;min_size);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;pointing&nbsp;to&nbsp;the&nbsp;same&nbsp;biggest&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(set.ceiling(l)&nbsp;!=&nbsp;set.floor(r))&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;has&nbsp;additional&nbsp;biggest&nbsp;besides&nbsp;[l,&nbsp;r]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(set.floor(l&nbsp;-&nbsp;1)&nbsp;!=&nbsp;null&nbsp;||&nbsp;set.ceiling(r&nbsp;+&nbsp;1)&nbsp;!=&nbsp;null)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;right_edge&nbsp;=&nbsp;set.ceiling(r&nbsp;+&nbsp;1)&nbsp;==&nbsp;null&nbsp;?&nbsp;Integer.MAX_VALUE&nbsp;:&nbsp;set.ceiling(r&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;left_edge&nbsp;=&nbsp;set.floor(l&nbsp;-&nbsp;1)&nbsp;==&nbsp;null&nbsp;?&nbsp;Integer.MIN_VALUE&nbsp;:&nbsp;set.floor(l&nbsp;-&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(&quot;draw&quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;min_size&nbsp;=&nbsp;Math.min(Math.max(right_edge,&nbsp;r)&nbsp;-&nbsp;l&nbsp;+&nbsp;1,&nbsp;r&nbsp;-&nbsp;Math.min(l,&nbsp;left_edge)&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(min_size&nbsp;==&nbsp;1&nbsp;?&nbsp;2&nbsp;:&nbsp;min_size);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(&quot;lose&quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(r&nbsp;==&nbsp;l&nbsp;?&nbsp;2&nbsp;:&nbsp;r&nbsp;-&nbsp;l&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(set.floor(l&nbsp;-&nbsp;1)&nbsp;!=&nbsp;null&nbsp;||&nbsp;set.ceiling(r&nbsp;+&nbsp;1)&nbsp;!=&nbsp;null)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;right_edge&nbsp;=&nbsp;set.ceiling(r&nbsp;+&nbsp;1)&nbsp;==&nbsp;null&nbsp;?&nbsp;Integer.MAX_VALUE&nbsp;:&nbsp;set.ceiling(r&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;left_edge&nbsp;=&nbsp;set.floor(l&nbsp;-&nbsp;1)&nbsp;==&nbsp;null&nbsp;?&nbsp;Integer.MIN_VALUE&nbsp;:&nbsp;set.floor(l&nbsp;-&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(&quot;draw&quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;min_size&nbsp;=&nbsp;Math.min(Math.max(r,&nbsp;right_edge)&nbsp;-&nbsp;l&nbsp;+&nbsp;1,&nbsp;r&nbsp;-&nbsp;Math.min(l,&nbsp;left_edge)&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(min_size&nbsp;==&nbsp;1&nbsp;?&nbsp;2&nbsp;:&nbsp;min_size);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(&quot;lose&quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(r&nbsp;==&nbsp;l&nbsp;?&nbsp;2&nbsp;:&nbsp;r&nbsp;-&nbsp;l&nbsp;+&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;}}