blocks|key|2511108|text|每当高度从左到右增加时，画笔笔触开始，当高度减小时，画笔笔触结束。你只需要看看它何时增加，因为如果你只计算每个笔划的起始点，你就会得到笔划计数。而不是在内部循环中循环高度级别，只需从前一个高度级别中减去一个高度级别即可得到差值。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2511109|在伪代码中：|2511110|int+BrushCount(int[]+buildings)
{
++++int+brushCount+=+0;
++++int+prevHeight+=+0;
++++for(int+i+=+0;+i+<+buildings.length;+i%2B%2B)
++++{
++++++++if(buildings[i]+>+prevHeight)
+++++++++++++brushCount+=+brushCount+%2B+(buildings[i]+-+prevHeight);
++++++++prevHeight+=+buildings[i];
++++}
++++return+brushCount;
}|code-block|syntax|javascript|2511111|在O(n)中运行。|2511112|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

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.

In pseudo-code:

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

Runs in O(n).

blocks|key|2511114|text|从数组末尾开始计数使用最后一个元素作为结果的初始值，并将前一个元素与当前元素进行比较。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2511115|如果它们是相同的值，则结果加1；如果前一个小于当前，则不做任何操作；如果前一个大于当前，则结果=结果%2B前一个-当前|2511116|int+i=sizeof+buildings;
int+t=buildings[i];+
while(i>0){
++if(buildings[i-1]-buildings[i]>0)+t%2B=(buildings[i-1]-buildings[i]);
++else+if(buildings[i-1]-buildings[i]==0)+%2B%2Bt;
++--i;
}
return+t;|code-block|syntax|javascript|2511117|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Counting from the end of the array use the last element as the initial value of the result, and compare the previous one with the current one. 

If they are the same value then, the result increase one;
 if the previous one is smaller than the current one, do nothing;
 if the previous one is bigger than the current one then, result = result +previous-current

<pre><code>int i=sizeof buildings;
int t=buildings[i]; 
while(i&gt;0){
 if(buildings[i-1]-buildings[i]&gt;0) t+=(buildings[i-1]-buildings[i]);
 else if(buildings[i-1]-buildings[i]==0) ++t;
 --i;
}
return t;
</code></pre>

blocks|key|2299300|text|一点高尔夫代码:)+(基于samgak出色的explanation。)|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2299301|​|2299302|const+f+=+A+=>+A.reduce((a,b,i,A)+=>+a+%2B+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]))|code-block|syntax|javascript|2299303|2299304|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/56373762/2034787^0|M|B|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]]|C|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|Y|8|@]|9|@]|C|$I|J]]|$1|K|3|E|5|6|7|Z|8|@]|9|@]|C|$]]|$1|L|3|-4|5|6|7|10|8|@]|9|@]|C|$]]]|M|$N|$5|O|P|Q|C|$R|S]]]]

A little code golf :) (Based on samgak's excellent <a href="https://stackoverflow.com/a/56373762/2034787">explanation</a>.)

<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>const f = A =&gt; A.reduce((a,b,i,A) =&gt; 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]))</code></pre>
</div>
</div>

blocks|key|2299314|text|public+static+int+brushCount(int[]+buildings)
{
++++int+count=0;
++++for(int+i=0;+i<=buildings.length-1;+i%2B%2B){
++++++++if((i%2B1)<(buildings.length)){
++++++++++++if(buildings[i]>buildings[i%2B1]){
++++++++++++++++count+%2B=+buildings[i]-buildings[i%2B1];
++++++++++++}
++++++++}else{
++++++++++++count+%2B=+buildings[i];
++++++++}+
++++}
++++return+count;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|2299315|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public static int brushCount(int[] buildings)
{
 int count=0;
 for(int i=0; i&lt;=buildings.length-1; i++){
 if((i+1)&lt;(buildings.length)){
 if(buildings[i]&gt;buildings[i+1]){
 count += buildings[i]-buildings[i+1];
 }
 }else{
 count += buildings[i];
 } 
 }
 return count;
}
</code></pre>

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

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

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

<a href="https://i.stack.imgur.com/Ojcdd.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Ojcdd.png" alt="enter image description here"></a>

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

<ul>
<li>The external loop running on the levels of each building (according to the highest building).</li>
<li>The inner loop is running on the array from <code>0</code> to <code>n</code>, and compares the difference of the height (<code>0</code> or <code>1</code>) between two near elements.</li>
</ul>

How can I do this in the <code>O(n)</code> time and <code>O(n)</code> space?

How can I count how many horizontal brush strokes are required to draw an array of buildings?

通过给定一个整数数组，每个元素表示一个建筑物。例如：int buildings[] = {1, 4, 3, 2, 3, 1}。如果我用画笔水平绘制建筑物，我会用多少画笔？我应该写一个函数来返回这些画笔笔划的数量。例如5。​​通过使用2个循环，我可以在运行时O(n^2)上轻松地做到这一点。在每个建筑物的级别上运行的外部循...

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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