Вопрос: задан массив целых чисел heights, представляющих высоту столбца гистограммы, где ширина каждого столбца равна 1, верните площадь самого большого прямоугольника на гистограмме.
Решение грубой силы.
для каждого бара, если мы найдем левую и правую границы прямоугольника, где текущий бар имеет минимальную высоту, мы можем вычислить площадь как
площадь = (правая[i]-левая[i]-1)*высота[i]
Пробный запуск с примером.
высоты = [2,1,5,6,2,3]
слева = [-1,0,1,2,1,4]
справа = [1,6,4,4,6,6]
площади = [(1-(-1)-1)*2, (6–0–1)*1, (4–1–1)*5, (4–2–1)*6, (6–1 –1)*2, (6–4–1)*3]
площади = [2, 5, 10, 6, 8, 3]
максимальная площадь = 10
Временная сложность O(N²)
Можем ли мы решить эту задачу за O(N)?
Что нам мешает с точки зрения временной сложности? Вложенный цикл while в строке № 8 и 15 в коде 1.
for(int i = 0; i < n; i++) {
int leftBoundary = i-1;
while(leftBoundary >= 0 && heights[leftBoundary] >= heights[i]){
leftBoundary--;
}
left[i] = leftBoundary;
}
Посмотрите внимательно на этот кусок кода. Мы вычисляем значения слева направо, в основном, мы вычисляем значение слева [i-1] до левого [i].
if(height[i-1] ≥ height[i]), то левая граница для i по крайней мере равна левой границе i-1. Подумайте об этом, попытайтесь понять это на примере
Так что мы можем сделать это
for(int i = 0; i < n; i++) {
int leftBoundary = i-1;
while(leftBoundary >= 0 && heights[leftBoundary] >= heights[i]){
leftBoundary = left[leftBoundary];
}
left[i] = leftBoundary;
}
Какова временная сложность этого кода сейчас.
Мы не сканируем повторно каждый элемент слева, вместо этого мы повторно используем ранее рассчитанные левые границы. Это сделает временную сложность от O(N²) до O(N)
О(N) код.
Это крутое решение.
Есть еще один способ решить эту проблему, который также довольно интуитивно понятен, если вы хорошо разбираетесь в решении проблем, основанных на стеке.
Если мы будем поддерживать стек возрастающей высоты и всякий раз, когда мы сталкиваемся с высотой, которая меньше, чем высота на вершине стека, мы достигаем правой границы для верхнего элемента стека.
Давайте разберемся на примере
высоты = [2,1,5,6,2,3]
stack = [-1] // поддерживать только индекс
- i = 0
- стек = [-1,0] maxArea = 0 - i = 1 // heights[1] ‹ height[stack.top]
- top = stack.pop() =› 0
- r = i =› 1, l = stack.top =› -1
- area = (r-l-1)*height[top] =› (1-(-1)-1)*2 =› 2
- stack.push(i)
- стек=[-1,1] - i = 2
- stack=[-1,1,2] as height[i] › height[stack.top] - i = 3
- стек=[-1,1,2,3] - i = 4
- верх = 3; стек.поп(); stack=[-1,1,2]
- r = 4, l = stack.top =› 2
- area = (4–2–1)*6 =› 6
- все еще height[i] ‹ height[stack.top] =› 2 ‹ 5
- top = 2; stack = [-1,1]
- r = 4, l = 1
- area = (4–1–1)*height[top] =› 2 * 5 =› 10
Код
Также см.:
Удачного кодирования!!!
