亚麻 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 I

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

sliding window确定processing power范围，用maxHeap track sliding window里 maximum booting power 的 index, clusterConsumption 没超就一直往右滑, 超了就左边++, 如果左边的index是maximum booting power, 就poll出来, 如果heap top的index不在sliding window范围里了也poll出来, 就一直能peek到sliding window范围里的max booting power，应该也能做？就是O(nlogn)到不了最优

用priority queue erase 的时候 是o(n)。这个应该用c++ map, bst.

int max_power_per_network(const vector<int> & process, const vector<int> & boot, int maxpower) {
    int i = 0, j = 0;
    int n = process.size();
    int sum = 0;
    map <int, int> maxboot;
    int ans = 0;
    while (j < n) {
        sum += process[j];
        maxboot[boot[j]]++;
        // compute consumption right now
        while (maxboot.rbegin()->first + sum * (j-i+1) > maxpower) {
            auto itr = maxboot.find(boot);
            if (itr->second > 1) {
                itr->second -= 1;
            } else {
                maxboot.erase(itr);
            }
            sum -= process[i];
            i += 1;
        }
        // update subarr length
        if (j - i + 1 > ans) {
            ans = j - i + 1;
        }
        j++;
    }
    return ans;
}[/i]

按照楼主的说法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)

匿名者 发表于 2022-2-25 17:27
按照楼主的说法monotonic queue + sliding window 应该可以实现O(N) 啊
i, j 从0 开始，j向右滑动，用mono ...

monotonic queue 本身应该不是O(1)的实现吧，所以整体复杂度应该不是O(N).

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