首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何计算绘制一组建筑物需要多少水平画笔笔划?

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

Stack Overflow用户
提问于 2019-05-30 15:23:22
回答 4查看 3.7K关注 0票数 27

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

如果我用画笔水平绘制建筑物,我会用多少画笔?

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

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

  • 在每个建筑物的级别上运行的外部循环(根据最高的建筑物)。
  • 内部循环在从0n的数组上运行,并比较两个邻近元素之间的高度差(01)。

我如何在O(n)时间和O(n)空间中做到这一点?

EN

回答 4

Stack Overflow用户

回答已采纳

发布于 2019-05-30 15:36:49

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

在伪代码中:

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

票数 20
EN

Stack Overflow用户

发布于 2019-05-30 22:48:15

一点高尔夫代码:) (基于samgak出色的explanation。)

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]))

票数 3
EN

Stack Overflow用户

发布于 2019-05-30 15:40:28

从数组末尾开始计数使用最后一个元素作为结果的初始值,并将前一个元素与当前元素进行比较。

如果它们是相同的值,则结果加1;如果前一个小于当前,则不做任何操作;如果前一个大于当前,则结果=结果+前一个-当前

int i=sizeof buildings;
int t=buildings[i]; 
while(i>0){
  if(buildings[i-1]-buildings[i]>0) t+=(buildings[i-1]-buildings[i]);
  else if(buildings[i-1]-buildings[i]==0) ++t;
  --i;
}
return t;
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/56373582

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档