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:
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;
}
Runs in O(n).