Doordash 新鲜面经

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

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

每次remove nums中的值，可以把priorityqueue里的做法移到你的第一个循环里。每次循环只poll一个最小的peak出来。然后把nums中的这个值remove掉。
好像还是不对，我这个时间复杂度是n2logn了。lz那个实在太复杂了。

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

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

我觉得完全可以用Double Linked List + PQ的结合来解题，思路非常类似LRU Cache蠡口幺丝溜。

闲来无事自己写了一个，下周准备面三哥。

1. import java.util.*;
   
2. 
   
3. class Solution {
   
4.     public int[] solve(int[] nums) {
   
5.         int[] result = new int[nums.length];
   
6. 
   
7.         PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
   
8. 
   
9.         Node head = new Node(Integer.MIN_VALUE);
   
10.         Node tail = new Node(Integer.MIN_VALUE);
    
11. 
    
12.         head.next = tail;
    
13.         tail.pre = head;
    
14. 
    
15.         for (int num : nums) {
    
16.             tail.insertBefore(new Node(num));
    
17.         }
    
18. 
    
19.         Node temp = head.next;
    
20.         while (temp.next != null) {
    
21.             if (temp.val > temp.pre.val && temp.val > temp.next.val) {
    
22.                 queue.add(temp);
    
23.             }
    
24.             temp = temp.next;
    
25.         }
    
26. 
    
27.         int index = 0;
    
28.         while (!queue.isEmpty()) {
    
29.             Node curr = queue.poll();
    
30.             result[index++] = curr.val;
    
31.             Node pre = curr.pre;
    
32.             Node next = curr.next;
    
33.             curr.removeSelf();
    
34.             if (pre != head && pre != tail && pre.val > pre.pre.val && pre.val > pre.next.val) {
    
35.                 queue.add(pre);
    
36.             }
    
37.             if (next != head && next != tail && next.val > next.pre.val
    
38.                 && next.val > next.next.val) {
    
39.                 queue.add(next);
    
40.             }
    
41.         }
    
42. 
    
43.         return result;
    
44.     }
    
45. 
    
46.     private class Node {
    
47.         Node pre;
    
48.         Node next;
    
49.         int val;
    
50. 
    
51.         Node(int v) {
    
52.             val = v;
    
53.         }
    
54. 
    
55.         private void insertBefore(Node toInsert) {
    
56.             this.pre.next = toInsert;
    
57.             toInsert.pre = this.pre;
    
58.             this.pre = toInsert;
    
59.             toInsert.next = this;
    
60.         }
    
61. 
    
62.         private void removeSelf() {
    
63.             this.pre.next = this.next;
    
64.             this.next.pre = this.pre;
    
65.         }
    
66.     }
    
67. }

复制代码

这难道不是单调栈可解吗?