улавливание дождевой воды - массив

Question

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

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

Например, если входной

[0,1,0,2,1,0,1,3,2,1,2,1] 

возвращаемое значение будет

6 

Решение в соответствии с ответом книги это

public class Solution { 
    public int trap(int[] height) { 
     if (height.length <=2) 
      return 0; 
     int h = 0, sum = 0, i = 0, j = height.length - 1; 
     while(i < j) 
     { 
      if (height[i] < height[j]) 
      { 
       h = Math.max(h,height[i]); 
       sum += h - height[i]; 
       i++; 
      } 
      else 
      { 
       h = Math.max(h,height[j]); 
       sum += h - height[j]; 
       j--; 
      } 
     } 
     return sum; 
    } 
} 

Благодаря

Answer 1

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

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

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

Первый столбец - высота и указатель возвышений слева. Второй столбец - это высота и индекс высот справа.

Третья колонка - максимальная минимальная высота. Другими словами, максимальная высота слева или справа, в зависимости от того, какой максимум меньше. Это число важно для определения местного уровня воды.

Четвертая колонка - это сумма.

Следуйте вместе с диаграммой, и вы можете увидеть, как работает алгоритм.

0,0 1,11 0 0 
1,1 1,11 1 0 
1,1 2,10 1 0 
0,2 2,10 1 1 
2,3 2,10 2 1 
2,3 1,9 2 2 
2,3 2,8 2 2 
2,3 3,7 2 2 
1,4 3,7 2 3 
0,5 3,7 2 5 
1,6 3,7 2 6 

6 

И вот код. Размещение инструкций print и println в соответствующих местах может помочь вам понять, что делает код.

package com.ggl.testing; 

public class RainWater implements Runnable { 

    public static void main(String[] args) { 
     new RainWater().run(); 
    } 

    @Override 
    public void run() { 
     int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; 
     System.out.println(trap(height)); 
    } 

    public int trap(int[] height) { 
     if (height.length <= 2) { 
      return 0; 
     } 

     int h = 0, sum = 0, i = 0, j = height.length - 1; 

     while (i < j) { 
      System.out.print(height[i] + "," + i + " " + height[j] + "," + j 
        + " "); 

      if (height[i] < height[j]) { 
       h = Math.max(h, height[i]); 
       sum += h - height[i]; 
       i++; 
      } else { 
       h = Math.max(h, height[j]); 
       sum += h - height[j]; 
       j--; 
      } 

      System.out.println(h + " " + sum); 
     } 

     return sum; 
    } 

} 

Answer 2

Я знаю, T шляпа, вероятно, это не самый лучший способ представить это графически, но вы можете себе представить ситуацию, как на следующем рисунке:

Где красные бары местность (с высотами в соответствии с матрицей вашего примера) , а синие полосы - это вода, которая может быть «захвачена» в «долины» местности.

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

Answer 3

Алгоритм работает путем обработки земли слева (i) и правой (j). i и j - это счетчики, которые работают друг против друга, приближаясь к середине земли.

h - переменная, которая отслеживает максимальную высоту, найденную до сих пор, учитывая нижнюю сторону.

Земля обрабатывается, позволяя i и j работать «друг к другу». Когда я прочитал код, я представил две воображаемые стены, сжимая воду к середине, где нижняя стена движется к более высокой стене. Алгоритм продолжает суммировать объем воды. Он использует h - height [x], потому что вода может содержаться только внутри самой низкой точки между двумя стенами. Таким образом, по существу, он продолжает суммировать объем воды слева и справа и вычитается, а вода перемещается более высокими блоками высоты.

Может быть лучше имена переменных были бы

• leftWall вместо я
• rightWall вместо J
• waterMaxHeight вместо Н

Answer 4

Я думаю, что выше решение трудно понять . У меня есть простое решение, которое принимает o (n) дополнительное пространство. & o (n) временная сложность.

Шаг алгоритма

1.Maintain массив, который содержит максимум всего элемента, который с правой стороны текущего элемента.

2.maintain переменная max с левой стороны, которая содержит максимум всего элемента, который находится слева от текущего элемента.

3.find минимум max слева & max справа, который уже присутствует в массиве.

4.if минимальное значение больше, чем текущее значение в массиве, чем разница в добавлении, чем в ans &, добавьте разницу с текущим значением & обновление максимума слева.

import java.util.*; 
 
import java.lang.*; 
 
import java.io.*; 
 

 

 
class Solution 
 
{ 
 
\t public static void main (String[] args) throws java.lang.Exception 
 
\t { 
 
\t \t int[] array= {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; 
 
\t \t int[] arrayofmax=new int[array.length]; 
 
\t \t int max=0; 
 
\t \t arrayofmax[array.length-1]=0; 
 
\t \t for(int x=array.length-1;x>0;x--){ 
 
\t \t  if(max<array[x]){ 
 
\t \t   max=array[x]; 
 
\t \t  } 
 
\t \t  arrayofmax[x-1]=max; 
 
\t \t } 
 
\t \t int ans=0; 
 
\t \t int maxfromleft=0; 
 
\t \t 
 
\t \t for(int i=0;i<array.length-1;i++){ 
 
\t \t  if(maxfromleft<array[i]){ 
 
\t \t   maxfromleft=array[i]; 
 
\t \t  } 
 
\t \t  int min=maxfromleft>arrayofmax[i+1]?arrayofmax[i+1]:maxfromleft; 
 
\t \t  if(min>array[i+1]){ 
 
\t \t   ans+=min-array[i+1]; 
 
\t \t   array[i+1]=min; 
 
\t \t  } 
 
\t \t } 
 
\t \t System.out.println(ans); 
 
\t } 
 
}

Может быть мой алгоритм такой же, как и выше, но я думаю, что эта реализация легко понять