algorithm - 如何解决这个问题？

Question

最近在我的面试中有人问我一个算法问题:

给定 n 行草的高度 H[n]。一个农民做了 k 次以下操作->
选择开始索引 (s)、结束索引 (e) 和高度 (h)。将他的修草仪器固定在高度 h 处，将草从第 s 行修剪到第 e 行。意思是，对于 s 和 e 之间的 i 的每个 H[i]，H[i]=min(H[i],h)。
打印 k 次操作后的所有高度。

注意 -> 如果 H[i] 为 6，h 为 4，则修剪后 H[i] 变为 4(不会减少 4)

禁止使用段/芬威克树，面试需要比 O(nk) 更好的东西。如何解决？

问题也可以在 http://www.geeksforgeeks.org/directi-interview-set-12-on-campus/(第四轮问题)

Answer 1

想法是删除冗余操作，然后只需执行一次 min(H[i],h) 即可遍历数组，保留所有高度设置，这将是 O(n)。删除冗余操作需要你对它们进行排序和一些 for，所以复杂度将是 O(n + klog(k) + k) = O(n + klog(k))。

要删除冗余操作，您将首先仅根据初始位置对它们进行排序。

然后:

for(int x=0;x<oper.length;x++){
    int curr = x+1;
    while(oper[curr].start<oper[x].end){
        if(oper[curr].height > oper[x].height)
            oper[curr].start = oper[x].end;// When you for through the operations you will go from the start to the end of it, if the start is after the end you will not trim
        else { // oper[curr].height<=oper[x].height
            if(oper[x].end<oper[curr].end){
                oper[x].end = oper[curr].start;
            }
            else {
                /**
                 * Make another operation that starts at the end of oper[curr]
                 * and ends at the end of oper[x], and insert it accordingly
                 * in oper. Then make oper[x] end at oper[curr].start
                 * */
            }
        }
        curr++;
    }
}
// Now no operation overlaps with one another.
// When operations where overlapping only the minimum was saved

// Now trim
for(int x = 0;x<oper.length;x++){
    for(int s = oper[x].start;s<oper[x].end;s++){
        h[s] = min(oper[x].height,h[s]);
    }
}

将此与 Dominique 保存高度的方法相结合，您将得到一个非常快的算法。