c - 在线练习技术面试，我错过了什么？

Question

我正在准备近期的工作面试，并参加了模拟技术测试。我在这些问题上做得很好，除了这个......

问题的前提是:给定一个数组，找到大小为“n”的数组的连续子集的最大差。示例

input = [6,8,4,5,3,1,7], n=3
[6,8,4] = the biggest diff = 4 (8-4)
[8,4,5] = the biggest diff = 4 (8-4)
[4,5,3] = 2
[5,3,1] = 4
[3,1,7] = 6
Final return from function:6

输入的限制类似于:数组的长度将小于 100k，n 将小于数组的长度。 函数必须在 2 秒内完成。

我最初是用 python 写的，但只收到 3/6 正确的测试用例，3 个由于时间限制而失败，所以我用 C 重写了希望获得更好的性能。

int i,j;
int maxdiff = 0;
int localmax,localmin,localdiff;
for (i=0;i<v_length-d+1;i++){
    localmax = v[i];
    localmin = v[i];
    localdiff = 0;
    for(j=0;j<d;j++){
        if(v[j+i] > localmax){
            localmax = v[j+i];
        }
        if(v[j+i] < localmin){
            localmin = v[j+i];
        }
    }
    localdiff = localmax-localmin;
    if(localdiff > maxdiff){
        maxdiff = localdiff;
    }
}
return maxdiff;

我试过运行它，但结果相同。 3/6 正确，3/6 由于运行时失败。

我是不是漏掉了什么？我意识到我循环遍历数组 ArraySize-n 次中的每个值，我可以在脑海中以某种方式想象可以只循环遍历数组一次，但似乎无法弄清楚如何。有什么建议吗？谢谢!

Answer 1

您可以在 O(nlogn) 中为子集使用一个最小堆和一个最大堆来完成此操作。在遍历数组期间从堆中移除第一个元素并添加新元素