如何计算绘制一组建筑物需要多少水平笔触？ [英] How can I count how many horizontal brush strokes are required to draw an array of buildings?

问题描述

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

By given an array of integers, each element represents a building. For example: int buildings[] = {1, 4, 3, 2, 3, 1}.

如果我用画笔水平绘制建筑物，我将使用多少画笔笔触？

If I drew the buildings horizontally with a brush, how many brush strike I would use?

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

I should write a function that returns the number of these brush strokes. For example 5.

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

I can do it easily on run time O(n^2), by using 2 loops.

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

• The external loop running on the levels of each building (according to the highest building).

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

The inner loop is running on the array from 0 to n, and compares the difference of the height (0 or 1) between two near elements.

如何在 O（n）时间和 O（n）空间？

推荐答案

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

A brush stroke starts whenever the height increases going from left to right, and ends when it decreases. You only need to look at when it increases, because if you just count the starting points of each stroke you will have the stroke count. Instead of looping over the height levels in an inner loop, just subtract one height level from the previous to get the difference.

在伪代码中：

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

这篇关于如何计算绘制一组建筑物需要多少水平笔触？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！