Как я могу посчитать, сколько горизонтальных мазков кисти требуется, чтобы нарисовать массив зданий?

По заданному массиву целых чисел каждый элемент представляет здание. Например: int buildings[] = {1, 4, 3, 2, 3, 1}.

Если бы я рисовал здания кистью по горизонтали, сколько мазков я бы использовал?

Я должен написать функцию, которая возвращает количество этих мазков. Например 5.

Я могу сделать это легко во время выполнения O(n^2), используя 2 цикла.

Внешний цикл работает на уровнях каждого здания (согласно самому высокому зданию).
Внутренний цикл выполняется в массиве от 0 до n и сравнивает разницу высот (0 или 1) между двумя ближайшими элементами.

Как я могу сделать это в O(n) времени и O(n) пространстве?

Ответ 1

Мазок кисти начинается всякий раз, когда высота увеличивается слева направо, и заканчивается, когда он уменьшается. Вам нужно только смотреть, когда он увеличивается, потому что если вы просто посчитаете начальные точки каждого удара, у вас будет счетчик ударов. Вместо того, чтобы зацикливаться на уровнях высоты во внутренней петле, просто вычтите один уровень высоты от предыдущего, чтобы получить разницу.

В псевдокоде:

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

Ответ 2

Немного кода для гольфа :) (На основе самгак отличное объяснение.)

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

При подсчете с конца массива используйте последний элемент в качестве начального значения результата и сравните предыдущий с текущим.

Если они имеют одинаковое значение, результат увеличивается на единицу; если предыдущий меньше текущего, ничего не делать; если предыдущий больше текущего, то результат = результат + предыдущий-текущий

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;