Алгоритм решения для накопления воды при заданных высотах здания

Я практикую алгоритмы, и я застрял в этой проблеме в течение нескольких дней. Когда я проверяю свое решение, я по-прежнему ошибаюсь. Вот описание проблемы:

Уолл-стрит в Нью-Йорке известна своими захватывающими небоскребами. Но сезон дождей приближается, и количество воды, которое будет падать над зданиями, будет огромным в этом году. Поскольку каждое здание прикреплено к зданиям слева и справа (за исключением первого и последнего), вода может течь из здания только в том случае, если высота здания выше высоты здания до его слева или справа (высота краев Уолл-стрит равна 0). Все здания имеют ширину 1 метр. Вам даны высоты (в метрах) зданий на Уолл-стрит слева направо, и ваша задача – напечатать на стандартном выводе (стандартное) общее количество воды (в кубических метрах), которая хранится над зданиями на Уолл-стрит ,

Пример ввода:

heights: [9 8 7 8 9 5 6] 

Пример вывода:

 5 

Объяснение: В этом примере между первым и пятым зданиями находятся 4 кубических метра воды (1 над вторым, 2 над третьим и 1 над четвертым), а между пятым и седьмым зданиями 1 кубический метр воды (более шестого здания).

Мой подход к этой проблеме – найти глобальные максимумы и использовать различия в этих максимумах для расчета накопления воды. Я учитываю воду, которую я, возможно, пропустил в конце, используя переменную local_water. Может ли кто-нибудь помочь мне найти ошибку в моем алгоритме или коде?

ПРИМЕЧАНИЕ. Я ищу решение, которое проходит через каждый элемент только один раз.

Вот вход, где у меня есть ошибка:

 heights: [8,8,4,5] 

этот ввод должен дать 1 , а не мой ответ, который равен 0 .

Вот мой код:

 def skyscrapers(heights): heights.insert(0,0) heights.append(0) local_max = 0 global_max = 0 total_water = 0 local_water = 0 end_water = [] # end_water records water heights to be used for finding # water between the final global maximum and # subsequent local maximums. These potential values are # stored in local_water. for i in range(1, len(heights)-1): end_water.append(heights[i]) # check for local max if heights[i-1] < heights[i] and heights[i] > heights[i+1]: # record potential collected water for after final # gloabl max for s in end_water: local_water += (heights[i] - s) * (heights[i] - s > 0) local_max=i # new global max if heights[local_max] > heights[global_max]: for s in heights[global_max:local_max]: if heights[global_max] - s > 0: total_water += heights[global_max] - s global_max = local_max local_water = 0 end_water = [] total_water += local_water print total_water 

3 Solutions collect form web for “Алгоритм решения для накопления воды при заданных высотах здания”

 height _ _ 9 | |_ _| | _ _ 8 | |_| | | | 7 | | _ | | 6 | |_| | | | _ 5 | | | |_| | 4 | | | | _ _ 3 | | | | | | _ | | 2 | | | | | |_| |_| | 1 |0 1 2 3 4 5 6| |0 1 2 3| |0 1 2 3 4| pos 

Вот однопроходный (!) (O (n) -time) O (n) -пространственный алгоритм, основанный на решении на основе стека для максимизации прямоугольной области в задаче Гистограмма :

 from collections import namedtuple Wall = namedtuple('Wall', 'pos height') def max_water_heldover(heights): """Find the maximum amount of water held over skyscrapers with *heights*.""" stack = [] water_held = 0 # the total amount of water held over skyscrapers for pos, height in enumerate(heights): while True: if not stack or height < stack[-1].height: # downhill stack.append(Wall(pos + 1, height)) # push possible left well wall break else: # height >= stack[-1].height -- found the right well wall/bottom bottom = stack.pop().height if stack: # if there is the left well wall well_height = min(stack[-1].height, height) - bottom if well_height: water_held += (pos - stack[-1].pos) * well_height return water_held 

Пример:

 >>> max_water_heldover([9, 8, 7, 8, 9, 5, 6]) 5 >>> max_water_heldover([8, 8, 4, 5]) 1 >>> max_water_heldover([3, 1, 2, 1, 3]) 5 

Я протестировал его против алгоритма O (n * m) грубой силы:

 from itertools import product def test(max_buildings=6, max_floors=6): for nbuildings, nfloors in product(range(max_buildings), range(max_floors)): for heights in product(range(nfloors), repeat=nbuildings): assert max_water_heldover(heights) == max_water_heldover_bruteforce(heights), heights 

где max_water_heldover_bruteforce() :

 import sys from colorama import Back, Fore, Style, init # $ pip install colorama init(strip=not sys.stderr.isatty()) def max_water_heldover_bruteforce(heights): if not heights: return 0 BUILDING, AIR, WATER = ['B', ' ', Back.BLUE + Fore.WHITE + 'W' + Fore.RESET + Back.RESET + Style.RESET_ALL] matrix = [[WATER] * len(heights) for _ in range(max(heights))] for current_floor, skyscrapers in enumerate(matrix, start=1): outside = True for building_number, building_height in enumerate(heights): if current_floor <= building_height: outside = False skyscrapers[building_number] = BUILDING elif outside: skyscrapers[building_number] = AIR for i, building_height in enumerate(reversed(heights), 1): if current_floor > building_height: skyscrapers[-i] = AIR else: break if '--draw-skyscrapers' in sys.argv: print('\n'.join(map(''.join, matrix[::-1])), file=sys.stderr) print('-'*60, file=sys.stderr) return sum(1 for row in matrix for cell in row if cell == WATER) 

Результаты те же.

 class Solution: # @param A, a list of integers # @return an integer def trap(self, A): uTrapper = [] i = 0 leftIndex = 0 rightIndex = 0 # only 2 left could not trap water while (i < (len(A) - 2)): leftIndex = self.findLeftBank((A[i:])) + i rightIndex = self.findRightBank((A[leftIndex+1:]), A[leftIndex]) + leftIndex + 1 uTrapper.append((A[leftIndex : rightIndex+1])) i = rightIndex return self.getRainWater(uTrapper) def findLeftBank(self, list): for i in range(len(list)): curr = list[i] currNext = list[i+1] if i+1 < len(list) else 0 if(curr > currNext): return i return len(list) - 1 def findRightBank(self, list, leftHight): biggestLoc = len(list) biggest = 0 for i in range(len(list)): if(list[i] >= leftHight): return i if(list[i] > biggest): biggestLoc = i biggest = list[i] return biggestLoc def getRainWater(self, lists): all = 0 for i in range(len(lists)): list = lists[i] height = min(list[0], list[len(list)-1]) for i in range(1, len(list)-1): if(list[i] > height): continue all = all + (height - list[i]) return all s = Solution() print s.trap([9,6,8,8,5,6,3]) 

Это нормально?

Вот однопроходное решение, которое улучшается на решениях liuzhidong и JS Sebastian, используя только O (1) пространство:

 def fillcount(elevations): start = 0 end = len(elevations) - 1 count = 0 leftmax = 0 rightmax = 0 while start < end: while start < end and elevations[start] <= elevations[start + 1]: start += 1 else: leftmax = elevations[start] while end > start and elevations[end] <= elevations[end - 1]: end -= 1 else: rightmax = elevations[end] if leftmax < rightmax: start += 1 while start < end and elevations[start] <= leftmax: count += leftmax - elevations[start] start += 1 else: end -= 1 while end > start and elevations[end] <= rightmax: count += rightmax - elevations[end] end -= 1 return count 

Я протестировал его против этого более простого двухпроходного решения:

 def fillcount_twopass(elevations): global_max = max(range(len(elevations)), key=lambda x: elevations[x]) count = 0 local_max = 0 for i in xrange(0, global_max): if elevations[i] > local_max: local_max = elevations[i] else: count += local_max - elevations[i] local_max = 0 for i in xrange(len(elevations) - 1, global_max, -1): if elevations[i] > local_max: local_max = elevations[i] else: count += local_max - elevations[i] return count 

Двухпроходное решение основано на следующей логике:

  1. Найти максимальный пик для всего графика – глобальный максимум.
  2. Сканирование с левой стороны в направлении максимального максимального пика. Следите за левым максимумом. Каждая ячейка, которая является а) ниже или на том же уровне, что и левый максимум , б) справа от левого максимума , а в) слева от глобального максимума будет содержать воду. Когда левый максимум увеличивается, он не влияет на ранние столбцы, но более поздние столбцы теперь удерживают воду на этом новом максимальном уровне.
  3. Сделайте то же самое справа, наоборот.

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

Однопроходное решение частично основано на идеях Марка Толонен . Это улучшает вышеизложенное, наблюдая, что мы можем делать как левый, так и правый проход одновременно, не зная глобального максимума . Это потому, что текущий максимум с обеих сторон либо больше, чем ниже, либо равен максимальному с другой стороны. Нижний максимум всегда будет ниже глобального максимума, даже если мы еще не знаем, что такое глобальный максимум, поэтому мы можем перейти оттуда к следующему локальному максимуму с этой стороны. Алгоритм в полной мере:

  1. Начните с указателей в start и в end списка и инициализируйте left_max , right_max и count до 0 .
  2. Сканировать вправо, увеличивая start до достижения максимального значения слева. Затем сканирование влево, уменьшение end до достижения максимального максимума.
  3. Из нижнего максимума продолжайте сканирование до тех пор, пока вы не достигнете столбца, большего локального максимума, подсчета заполняемых ячеек по пути и добавления их к count .
  4. Повторите шаги 2 и 3, заканчивая, когда start и end совпадают.

Обратите внимание, что для наших целей местный максимум – это просто любая точка, которой предшествует восхождение (и, возможно, плато), а затем спуск. Локальные максимумы ниже максимального локального максимума, встречающегося до сих пор, встречаются только на шаге 3, где они не имеют эффекта.

Это последнее решение может обрабатывать десять миллионов точек данных за 3 секунды:

 >>> rands = [random.randrange(0, 1000000) for i in xrange(10000000)] >>> %timeit fillcount(rands) 1 loops, best of 3: 3.3 s per loop 
  • Я не могу напечатать окончательное значение переменной
  • Найти ближайший float в массиве для всех поплавков в другом массиве
  • Трассировка в динамическом программировании алгоритма Needleman-Wunsch
  • Самая длинная равноотстоящая подпоследовательность
  • Алгоритм решения точек и ящиков
  • Проверьте, является ли число рациональным в Python
  • Эффективное сокращение нескольких тензоров в Python
  • Как распознать элемент кортежа?
  • Минимаксный алгоритм Блэкджека
  • Алгоритм размещения сетки по неупорядоченному множеству точек
  • Как я могу проанализировать или улучшить простой алгоритм сжатия моей племянницы, основанный на коде Морзе?
  • Python - лучший язык программирования в мире.