通过给定一个整数数组,每个元素表示一个建筑物。例如:int buildings[] = {1, 4, 3, 2, 3, 1}
。
如果我用画笔水平绘制建筑物,我会用多少画笔?
我应该写一个函数来返回这些画笔笔划的数量。例如5
。
通过使用2个循环,我可以在运行时O(n^2)
上轻松地做到这一点。
0
到n
的数组上运行,并比较两个邻近元素之间的高度差(0
或1
)。我如何在O(n)
时间和O(n)
空间中做到这一点?
发布于 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)中运行。
发布于 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]))
发布于 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;
https://stackoverflow.com/questions/56373582
复制相似问题