如何计算绘制一系列建筑物需要多少水平画笔笔划?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (6)

通过给定一个整数数组,每个元素代表一个建筑物。例如:int buildings[] = {1, 4, 3, 2, 3, 1}

如果我用刷子水平地画出建筑物,我会使用多少次刷击?

我应该编写一个函数来返回这些笔触的数量。例如5

我可以O(n^2)通过使用2个循环在运行时轻松完成。

  • 外部循环在每个建筑物的层面上运行(根据最高建筑物)。
  • 内回路在阵列上运行从0n,并且高度(的差进行比较01两个近元件之间)。

我怎样才能做到这一点的O(n)时间和O(n)空间?

提问于
用户回答回答于

每当高度从左向右增加时,画笔笔划就会开始,并在高度减小时结束。您只需要查看它何时增加,因为如果您只计算每个笔划的起点,您将获得笔划数。而不是在内部循环中循环高度级别,只需从前一个高度级别中减去一个高度级别即可获得差异。

在伪代码中:

int BrushCount(int[] buildings)
{
    int brushCount = 0;
    int prevHeight = 0;
    for(int i = 0; i < buildings.length; i++)
    {
        if(buildings[i] > prevHeight)
             brushCount = brushCount + (buildings[i] - prevHeight);
        prevHeight = buildings[i];
    }
    return brushCount;
}

在O(n)中运行。

用户回答回答于

一点点代码高尔夫:):基于samgak的优秀解释。)

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

扫码关注云+社区

领取腾讯云代金券