如何计算绘制一组建筑物需要多少水平笔触？

Question

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

如果我用刷子水平绘制建筑物，我将使用多少次刷子打击？

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

O(n^2)通过使用2个循环，我可以在运行时轻松地做到这一点。

• 在每个建筑物（根据最高建筑物）的层上运行的外部循环。

• 内部循环从0到在数组上运行n，并比较两个邻近元素之间的高度差（0或1）。

我该如何在O(n)时间和O(n)空间上做到这一点？

Answer 1

每当高度从左到右增加时，画笔笔划就开始；当高度减小时，画笔笔划就结束。您只需要查看它增加的时间，因为如果您仅计算每个笔画的起点，您将获得笔画数。与其在内部循环中遍历高度水平，不如从前一个高度中减去一个高度水平即可得到差值。

用伪代码：

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）中运行。