亚麻 OA 解法

题目是近期亚麻oa 原题， 我只能想出n2 解法， 尝试了sliding window + monotonic queue 没找到o(n) 解法。
有没有大神给指点下，回复解法加米谢谢🙏

AWS has several data centers which have multiple processors that perform computations. In one such data center, these processors are placed in a sequence with their IDs den

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

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

defined as : max booting Power[i], booting Power[i+1], ...., booting power[i+k-1]

return the max cluster per net power consumption.

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

按照楼主的说法monotonic queue + sliding window 应该可以实现O(N) 啊
i, j 从0 开始，j向右滑动，用monotic queue来找最大值，然后再用一个变量来求和，发现超过最大power的时候停止，这个时候就涵盖了起点为i的最长可能值
然后i从右移动1个，再来滑j，只有向右，不可能向左，这样就没个entry都只是被访问了一次，所以应该是O(N)

请问楼主是ng还是社招？

匿名者 发表于 2022-2-25 11:36
请问楼主是ng还是社招？

社招， 不是ng

匿名者 发表于 2022-2-26 01:18
sliding window确定processing power范围，用maxHeap track sliding window里 maximum booting power 的 in ...

谢谢， 已加米

nod，mono stack+sliding window的组合，就是O(n)

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

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

n < 10^5,  n^2 algorithm 實測可以過所有test case嗎?