倒呆死店面

面试官是个三姐， 口音比较重

给一个array，

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

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

不知道lc 有没有原题，请告知

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

1. <font style="vertical-align: inherit;"><font style="vertical-align: inherit;"><font style="vertical-align: inherit;"><font style="vertical-align: inherit;"></font></font><font style="vertical-align: inherit;"><font style ="vertical-align: inherit;"></font></font></font></font>

复制代码

1. linear scan 把所有的 local peak 放进 min-heap 里面
2. 每次从min_heap pop 的时候检查左右两边是否成为新的 local peak, 然后放进 min-heap
如果 step2 没有优化最糟糕情况是 O(n^2)
时间复杂度要求比 O(n^2) 更好吗？

拓扑排序
维护每个数indegree, left(左边的数的index), right(右边的数的index) -- 这里left和right相当于graph里的edges
indegree加1如果两边有比这个数大的数
每次pop 维护 左右的indegree,left,right （indegree为0的时候enqueue）
这样能O(n)?

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

这个array里面有重复的数值吗？
如果有的话，是不是在任何一个时候，只弹出一个或者弹出所有相同的？
因为这一步会影响下一步的数值选择。

大熊小熊 发表于 2023-8-29 18:06
感觉在你这个思路的基础上，如果用linkedlist来表示节点，这样删除和检查两边的操作就从O(n)降低成了O(1) ...

这个思路不错！

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

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

1.     public int[] popLocalPeak(int[] input) {

复制代码

double linked list
time complexity: NlgN worst case
space complexity: N