本文概述

• C++
• Java
• Python3
• C++
• Java
• Python3
• C#
• 的PHP
• C++
• Java
• Python3
• C#
• 的PHP
• C++
• Java
• Python3
• C++
• Java

给定n个代表高程图的非负整数, 其中每个条的宽度为1, 计算下雨后它能捕集多少水。
例子:

Input: arr[]= {2, 0, 2} Output: 2 Explanation: The structure is like below

文章图片

We can trap 2 units of water in the middle gap.Input: arr[]= {3, 0, 2, 0, 4} Output: 7 Explanation: Structure is like below

文章图片

We can trap "3 units" of water between 3 and 2, "1 unit" on top of bar 2 and "3 units" between 2 and 4.See below diagram also.Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6Explanation: The structure is like below

文章图片

Trap "1 unit" between first 1 and 2, "4 units" between first 2 and 3 and "1 unit" between second last 1 and last 2

基本思路：
如果左右两侧有较高的条形, 则数组的元素可以存储水。可以通过找到左侧和右侧条形的高度来找出要存储在每个元素中的水量。这个想法是计算可以存储在数组的每个元素中的水量。
例子
考虑数组{3, 0, 0, 2, 0, 4}, 可以存储三个单位的水三个索引1和2, 在索引3处存储一个水, 在索引4中存储三个水。

对于Array [] = {3, 0, 2, 0, 4}存储的水= 0 + 3 + 1 + 3 + 0 = 7

方法1：
这是解决上述问题的简单方法。

• 方法：这个想法是遍历每个数组元素, 并在左侧和右侧找到最高的条形。取两个高度中的较小者。当前元素的较小高度和高度之间的差是可以存储在此数组元素中的水量。
• 算法： 
  1. 从头到尾遍历数组。
  2. 对于每个元素, 从开始到该索引遍历数组, 然后找到最大高度(一种)并从当前索引遍历数组到结尾并找到最大高度(b).
  3. 将在此列中存储的水量为min(a, b)–数组[i], 将此值添加到存储的水总量中
  4. 打印存储的水总量。
• 实现 
   

C++

//C++ implementation of the approach #include< bits/stdc++.h> using namespace std; //Function to return the maximum //water that can be stored int maxWater( int arr[], int n) {//To store the maximum water //that can be stored int res = 0; //For every element of the array for ( int i = 1; i < n-1; i++) {//Find the maximum element on its left int left = arr[i]; for ( int j=0; j< i; j++) left = max(left, arr[j]); //Find the maximum element on its right int right = arr[i]; for ( int j=i+1; j< n; j++) right = max(right, arr[j]); //Update the maximum water res = res + (min(left, right) - arr[i]); }return res; } //Driver code int main() { int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; int n = sizeof (arr)/sizeof (arr[0]); cout < < maxWater(arr, n); return 0; }

Java

//Java implementation of the approach class GFG{//Function to return the maximum //water that can be stored public static int maxWater( int [] arr, int n) {//To store the maximum water //that can be stored int res = 0 ; //For every element of the array //except first and last element for ( int i = 1 ; i < n - 1 ; i++) {//Find maximum element on its left int left = arr[i]; for ( int j = 0 ; j < i; j++) { left = Math.max(left, arr[j]); }//Find maximum element on its right int right = arr[i]; for ( int j = i + 1 ; j < n; j++) { right = Math.max(right, arr[j]); }//Update maximum water value res += Math.min(left, right) - arr[i]; } return res; }//Driver code public static void main(String[] args) { int [] arr = { 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 }; int n = arr.length; System.out.print(maxWater(arr, n)); } }//This code is contributed by Debidutta Rath

Python3

# Python3 implementation of the approach # Function to return the maximum # water that can be stored def maxWater(arr, n) :# To store the maximum water # that can be stored res = 0 ; # For every element of the array for i in range ( 1 , n - 1 ) : # Find the maximum element on its left left = arr[i]; for j in range (i) : left = max (left, arr[j]); # Find the maximum element on its right right = arr[i]; for j in range (i + 1 , n) : right = max (right, arr[j]); # Update the maximum water res = res + ( min (left, right) - arr[i]); return res; # Driver code if __name__ = = "__main__" : arr = [ 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ]; n = len (arr); print (maxWater(arr, n)); # This code is contributed by AnkitRai01

输出如下：

6

• 复杂度分析： 
  • 时间复杂度：O(n^2)。
    有两个遍历数组的嵌套循环, 因此时间复杂度为O(n^2)。
  • 空间复杂度：O(1)。
    不需要额外的空间。

方法2：
这是解决上述问题的有效方法。

• 方法：在先前的解决方案中, 要在左侧和右侧找到最高的条形, 需要遍历数组, 这会降低解决方案的效率。为了提高效率, 必须在线性时间内预先计算每个小节左右两边的最高小节。然后使用这些预先计算的值来查找每个数组元素中的水量。
• 算法： 
  1. 创建两个数组剩下和对大小为n。创建一个变量max_ = INT_MIN.
  2. 从头到尾运行一个循环。在每次迭代中, 将max_更新为max_ = max(max_, arr [i])并分配左[i] = max_
  3. 更新max_ = INT_MIN。
  4. 从头到尾运行另一个循环。在每次迭代中, 将max_更新为max_ = max(max_, arr [i])并分配右[i] = max_
  5. 从头到尾遍历数组。
  6. 将在此列中存储的水量为min(a, b)–数组[i], (其中a =左[i], b =右[i])将此值加到存储的水总量中
  7. 打印存储的水总量。
• 实现 
   

C++

//C++ program to find maximum amount of water that can //be trapped within given set of bars. #include < bits/stdc++.h> using namespace std; int findWater( int arr[], int n) { //left[i] contains height of tallest bar to the //left of i'th bar including itself int left[n]; //Right [i] contains height of tallest bar to //the right of ith bar including itself int right[n]; //Initialize result int water = 0; //Fill left array left[0] = arr[0]; for ( int i = 1; i < n; i++) left[i] = max(left[i - 1], arr[i]); //Fill right array right[n - 1] = arr[n - 1]; for ( int i = n - 2; i> = 0; i--) right[i] = max(right[i + 1], arr[i]); //Calculate the accumulated water element by element //consider the amount of water on i'th bar, the //amount of water accumulated on this particular //bar will be equal to min(left[i], right[i]) - arr[i] . for ( int i = 0; i < n; i++) water += min(left[i], right[i]) - arr[i]; return water; }//Driver program int main() { int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; int n = sizeof (arr) /sizeof (arr[0]); cout < < "Maximum water that can be accumulated is " < < findWater(arr, n); return 0; }

Java

//Java program to find maximum amount of water that can //be trapped within given set of bars.class Test { static int arr[] = new int [] { 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 }; //Method for maximum amount of water static int findWater( int n) { //left[i] contains height of tallest bar to the //left of i'th bar including itself int left[] = new int [n]; //Right [i] contains height of tallest bar to //the right of ith bar including itself int right[] = new int [n]; //Initialize result int water = 0 ; //Fill left array left[ 0 ] = arr[ 0 ]; for ( int i = 1 ; i < n; i++) left[i] = Math.max(left[i - 1 ], arr[i]); //Fill right array right[n - 1 ] = arr[n - 1 ]; for ( int i = n - 2 ; i> = 0 ; i--) right[i] = Math.max(right[i + 1 ], arr[i]); //Calculate the accumulated water element by element //consider the amount of water on i'th bar, the //amount of water accumulated on this particular //bar will be equal to min(left[i], right[i]) - arr[i] . for ( int i = 0 ; i < n; i++) water += Math.min(left[i], right[i]) - arr[i]; return water; }//Driver method to test the above function public static void main(String[] args) {System.out.println( "Maximum water that can be accumulated is " + findWater(arr.length)); } }

Python3

# Python program to find maximum amount of water that can # be trapped within given set of bars.def findWater(arr, n):# left[i] contains height of tallest bar to the # left of i'th bar including itself left = [ 0 ] * n# Right [i] contains height of tallest bar to # the right of ith bar including itself right = [ 0 ] * n# Initialize result water = 0# Fill left array left[ 0 ] = arr[ 0 ] for i in range ( 1 , n): left[i] = max (left[i - 1 ], arr[i])# Fill right array right[n - 1 ] = arr[n - 1 ] for i in range (n - 2 , - 1 , - 1 ): right[i] = max (right[i + 1 ], arr[i]); # Calculate the accumulated water element by element # consider the amount of water on i'th bar, the # amount of water accumulated on this particular # bar will be equal to min(left[i], right[i]) - arr[i] . for i in range ( 0 , n): water + = min (left[i], right[i]) - arr[i]return water# Driver programarr = [ 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ] n = len (arr) print ( "Maximum water that can be accumulated is" , findWater(arr, n))# This code is contributed by # Smitha Dinesh Semwal

C#

//C# program to find maximum amount of water that can //be trapped within given set of bars. using System; class Test { static int [] arr = new int [] { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; //Method for maximum amount of water static int findWater( int n) { //left[i] contains height of tallest bar to the //left of i'th bar including itself int [] left = new int [n]; //Right [i] contains height of tallest bar to //the right of ith bar including itself int [] right = new int [n]; //Initialize result int water = 0; //Fill left array left[0] = arr[0]; for ( int i = 1; i < n; i++) left[i] = Math.Max(left[i - 1], arr[i]); //Fill right array right[n - 1] = arr[n - 1]; for ( int i = n - 2; i> = 0; i--) right[i] = Math.Max(right[i + 1], arr[i]); //Calculate the accumulated water element by element //consider the amount of water on i'th bar, the //amount of water accumulated on this particular //bar will be equal to min(left[i], right[i]) - arr[i] . for ( int i = 0; i < n; i++) water += Math.Min(left[i], right[i]) - arr[i]; return water; }//Driver method to test the above function public static void Main() {Console.WriteLine( "Maximum water that can be accumulated is " + findWater(arr.Length)); } }//This code is contributed by vt_m.

的PHP

< ?php //PHP program to find maximum //amount of water that can //be trapped within given set of bars.function findWater( $arr , $n ) {//left[i] contains height of //tallest bar to the //left of i'th bar including //itself //Right [i] contains height //of tallest bar to the right //of ith bar including itself //$right[$n]; //Initialize result $water = 0; //Fill left array $left [0] = $arr [0]; for ( $i = 1; $i < $n ; $i ++) $left [ $i ] = max( $left [ $i - 1], $arr [ $i ]); //Fill right array $right [ $n - 1] = $arr [ $n - 1]; for ( $i = $n - 2; $i> = 0; $i --) $right [ $i ] = max( $right [ $i + 1], $arr [ $i ]); //Calculate the accumulated //water element by element //consider the amount of //water on i'th bar, the //amount of water accumulated //on this particular //bar will be equal to min(left[i], //right[i]) - arr[i] . for ( $i = 0; $i < $n ; $i ++) $water += min( $left [ $i ], $right [ $i ]) - $arr [ $i ]; return $water ; }//Driver program $arr = array (0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1); $n = sizeof( $arr ); echo "Maximum water that can be accumulated is " , findWater( $arr , $n ); //This code is contributed by ajit ?>

• 输出如下： 
   

Maximum water that can be accumulated is 6

• 复杂度分析： 
  • 时间复杂度：上)。
    只需要遍历数组一次, 因此时间复杂度为O(n)。
  • 空间复杂度：上)。
    需要两个额外的数组, 每个数组的大小为n。
• 以上解决方案的空间优化：代替维护两个大小为n的数组来存储每个元素的左右最大值, 而是维护两个变量以存储最大值直到该点。由于水被困在任何元素上=min(max_left, max_right)– arr [i]。首先计算从Alo和Ahi中捕获在较小元素上的水, 然后将指针移动到lo不交叉hi.
• 实现 
   

C++

//C++ program to find maximum amount of water that can //be trapped within given set of bars. //Space Complexity : O(1)#include < iostream> using namespace std; int findWater( int arr[], int n) { //initialize output int result = 0; //maximum element on left and right int left_max = 0, right_max = 0; //indices to traverse the array int lo = 0, hi = n - 1; while (lo < = hi) { if (arr[lo] < arr[hi]) { if (arr[lo]> left_max) //update max in left left_max = arr[lo]; else //water on curr element = max - curr result += left_max - arr[lo]; lo++; } else { if (arr[hi]> right_max) //update right maximum right_max = arr[hi]; else result += right_max - arr[hi]; hi--; } }return result; }int main() { int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; int n = sizeof (arr) /sizeof (arr[0]); cout < < "Maximum water that can be accumulated is " < < findWater(arr, n); }//This code is contributed by Aditi Sharma

Java

//JAVA Code For Trapping Rain Water import java.util.*; class GFG {static int findWater( int arr[], int n) { //initialize output int result = 0 ; //maximum element on left and right int left_max = 0 , right_max = 0 ; //indices to traverse the array int lo = 0 , hi = n - 1 ; while (lo < = hi) { if (arr[lo] < arr[hi]) { if (arr[lo]> left_max)//update max in left left_max = arr[lo]; else//water on curr element = //max - curr result += left_max - arr[lo]; lo++; } else { if (arr[hi]> right_max)//update right maximum right_max = arr[hi]; else result += right_max - arr[hi]; hi--; } }return result; }/* Driver program to test above function */ public static void main(String[] args) { int arr[] = { 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 }; int n = arr.length; System.out.println( "Maximum water that " + "can be accumulated is " + findWater(arr, n)); } } //This code is contributed by Arnav Kr. Mandal.

Python3

# Python program to find # maximum amount of water that can # be trapped within given set of bars. # Space Complexity : O(1)def findWater(arr, n):# initialize output result = 0# maximum element on left and right left_max = 0 right_max = 0# indices to traverse the array lo = 0 hi = n - 1while (lo < = hi): if (arr[lo] < arr[hi]):if (arr[lo]> left_max):# update max in left left_max = arr[lo] else :# water on curr element = max - curr result + = left_max - arr[lo] lo + = 1else :if (arr[hi]> right_max): # update right maximum right_max = arr[hi] else : result + = right_max - arr[hi] hi - = 1return result# Driver programarr = [ 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ] n = len (arr)print ( "Maximum water that can be accumulated is " , findWater(arr, n))# This code is contributed # by Anant Agarwal.

C#

//C# Code For Trapping Rain Water using System; class GFG {static int findWater( int [] arr, int n) { //initialize output int result = 0; //maximum element on left and right int left_max = 0, right_max = 0; //indices to traverse the array int lo = 0, hi = n - 1; while (lo < = hi) { if (arr[lo] < arr[hi]) { if (arr[lo]> left_max)//update max in left left_max = arr[lo]; else//water on curr element = //max - curr result += left_max - arr[lo]; lo++; } else { if (arr[hi]> right_max)//update right maximum right_max = arr[hi]; else result += right_max - arr[hi]; hi--; } }return result; }//Driver program public static void Main() { int [] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; int result = Trap.findWater(arr, arr.length); System. out .print( " Total trapping water: " + result); } }//This code is contributed by vt_m.

的PHP

< ?php //PHP program to find maximum amount //of water that can be trapped within //given set of bars.//Method to find maximum amount //of water that can be trapped within //given set of bars. function findWater( $arr , $n ) {//initialize output $result = 0; //maximum element on //left and right $left_max = 0; $right_max = 0; //indices to traverse //the array $lo = 0; $hi = $n - 1; while ( $lo < = $hi ) { if ( $arr [ $lo ] < $arr [ $hi ]) { if ( $arr [ $lo ]> $left_max )//update max in left $left_max = $arr [ $lo ]; else//water on curr //element = max - curr $result += $left_max - $arr [ $lo ]; $lo ++; } else { if ( $arr [ $hi ]> $right_max )//update right maximum $right_max = $arr [ $hi ]; else $result += $right_max - $arr [ $hi ]; $hi --; } }return $result ; }//Driver Code $arr = array (0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1); $n = count ( $arr ); echo "Maximum water that can be accumulated is " , findWater( $arr , $n ); //This code is contributed by anuj_67. ?>

• 输出如下:
   

Maximum water that can be accumulated is 6

• 复杂度分析： 
  • 时间复杂度：O(n)。
    只需遍历数组。
  • 辅助空间：O(1)。
    由于不需要额外的空间。
• 感谢Gaurav Ahirwar和Aditi Sharma提供上述解决方案。 
   

方法3：
这里显示了另一个有效的解决方案。

• 方法：这里的概念是, 如果右侧有较大的墙, 则可以保留与左侧较小的墙相同高度的水。如果右侧没有较大的墙, 则从左侧开始。现在左侧必须有一堵更大的墙。让我们举个例子, 如果高度为{…。, 3, 2, 1, 4, ....}, 那么这里3和4是边界, 高度2和1被淹没并且不能充当边界。因此, 在数组的其余部分中存在更高或相等长度的边界时, 在任何点或索引处都知道前一个边界就足够了。如果不是, 则向后遍历数组, 现在必须在左侧留一堵更大的墙。
   
• 算法： 
  • 从索引0循环到给定数组的末尾。
  • 如果遇到大于或等于前一个墙的墙, 请在称为prev_index的变量中记录该墙的索引。
  • 继续添加前一堵墙的高度减去当前高度(ith)墙壁上的可变水。
  • 有一个临时变量, 该变量存储与水相同的值。
  • 如果没有发现大于或等于前一个墙的墙, 则退出。
  • 如果prev_index < 输入数组的大小, 则从水中减去temp变量, 然后从输入数组的末尾循环到prev_index, 并找到大于或等于前一堵墙的墙(在这种情况下, 从后向查找最后一堵墙)。
• 实现 
   

C++

//C++ implementation of the approach #include< iostream> using namespace std; //Function to return the maximum //water that can be stored int maxWater( int arr[], int n) { int size = n - 1; //Let the first element be stored as //previous, we shall loop from index 1 int prev = arr[0]; //To store previous wall's index int prev_index = 0; int water = 0; //To store the water until a larger wall //is found, if there are no larger walls //then delete temp value from water int temp = 0; for ( int i = 1; i < = size; i++) {//If the current wall is taller than //the previous wall then make current //wall as the previous wall and its //index as previous wall's index //for the subsequent loops if (arr[i]> = prev) { prev = arr[i]; prev_index = i; //Because larger or same //height wall is found temp = 0; } else {//Since current wall is shorter than //the previous, we subtract previous //wall's height from the current wall's //height and add it to the water water += prev - arr[i]; //Store the same value in temp as well //If we dont find any larger wall then //we will subtract temp from water temp += prev - arr[i]; } }//If the last wall was larger than or equal //to the previous wall then prev_index would //be equal to size of the array (last element) //If we didn't find a wall greater than or equal //to the previous wall from the left then //prev_index must be less than the index //of the last element if (prev_index < size) {//Temp would've stored the water collected //from previous largest wall till the end //of array if no larger wall was found then //it has excess water and remove that //from water variable water -= temp; //We start from the end of the array, //so previous should be assigned to //the last element prev = arr[size]; //Loop from the end of array up to the //previous index which would contain //the largest wall from the left for ( int i = size; i> = prev_index; i--) {//Right end wall will be definitely //smaller than the 'previous index' wall if (arr[i]> = prev) { prev = arr[i]; } else { water += prev - arr[i]; } } }//Return the maximum water return water; }//Driver Code int main() { int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; int n = sizeof (arr) /sizeof (arr[0]); cout < < maxWater(arr, n); return 0; }//This code is contributed by Debidutta Rath

Java

//Java implementation of the approach class GFG {//Function to return the maximum //water that can be stored public static int maxWater( int arr[], int n) { int size = n - 1 ; //Let the first element be stored as //previous, we shall loop from index 1 int prev = arr[ 0 ]; //To store previous wall's index int prev_index = 0 ; int water = 0 ; //To store the water until a larger wall //is found, if there are no larger walls //then delete temp value from water int temp = 0 ; for ( int i = 1 ; i < = size; i++) {//If the current wall is taller than //the previous wall then make current //wall as the previous wall and its //index as previous wall's index //for the subsequent loops if (arr[i]> = prev) { prev = arr[i]; prev_index = i; //Because larger or same height wall is found temp = 0 ; } else {//Since current wall is shorter than //the previous, we subtract previous //wall's height from the current wall's //height and add it to the water water += prev - arr[i]; //Store the same value in temp as well //If we dont find any larger wall then //we will subtract temp from water temp += prev - arr[i]; } }//If the last wall was larger than or equal //to the previous wall then prev_index would //be equal to size of the array (last element) //If we didn't find a wall greater than or equal //to the previous wall from the left then //prev_index must be less than the index //of the last element if (prev_index < size) {//Temp would've stored the water collected //from previous largest wall till the end //of array if no larger wall was found then //it has excess water and remove that //from 'water' var water -= temp; //We start from the end of the array, so previous //should be assigned to the last element prev = arr[size]; //Loop from the end of array up to the 'previous index' //which would contain the "largest wall from the left" for ( int i = size; i> = prev_index; i--) {//Right end wall will be definitely smaller //than the 'previous index' wall if (arr[i]> = prev) { prev = arr[i]; } else { water += prev - arr[i]; } } }//Return the maximum water return water; }//Driver code public static void main(String[] args) { int arr[] = { 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 }; int n = arr.length; System.out.print(maxWater(arr, n)); } }

Python3

# Pythpn3 implementation of the approach# Function to return the maximum # water that can be stored def maxWater(arr, n): size = n - 1# Let the first element be stored as # previous, we shall loop from index 1 prev = arr[ 0 ]# To store previous wall's index prev_index = 0 water = 0# To store the water until a larger wall # is found, if there are no larger walls # then delete temp value from water temp = 0 for i in range ( 1 , size + 1 ):# If the current wall is taller than # the previous wall then make current # wall as the previous wall and its # index as previous wall's index # for the subsequent loops if (arr[i]> = prev): prev = arr[i] prev_index = i# Because larger or same height wall is found temp = 0 else :# Since current wall is shorter than # the previous, we subtract previous # wall's height from the current wall's # height and add it to the water water + = prev - arr[i]# Store the same value in temp as well # If we dont find any larger wall then # we will subtract temp from water temp + = prev - arr[i]# If the last wall was larger than or equal # to the previous wall then prev_index would # be equal to size of the array (last element) # If we didn't find a wall greater than or equal # to the previous wall from the left then # prev_index must be less than the index # of the last element if (prev_index < size):# Temp would've stored the water collected # from previous largest wall till the end # of array if no larger wall was found then # it has excess water and remove that # from 'water' var water - = temp# We start from the end of the array, so previous # should be assigned to the last element prev = arr[size]# Loop from the end of array up to the 'previous index' # which would contain the "largest wall from the left" for i in range (size, prev_index - 1 , - 1 ):# Right end wall will be definitely smaller # than the 'previous index' wall if (arr[i]> = prev): prev = arr[i] else : water + = prev - arr[i]# Return the maximum water return water# Driver code arr = [ 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ] n = len (arr) print (maxWater(arr, n))# This code is contributed by Mohit Kumar

输出如下：

6

• 复杂度分析： 
  • 时间复杂度：O(n)。
    由于只需要遍历该数组。
  • 辅助空间：O(1)。
    由于不需要额外的空间。

【算法题（雨水捕获问题介绍和解决）】方法4(使用栈)：
我们可以使用Stack来跟踪由较长的左右栏所限制的栏。只能使用Stacks进行一次迭代来完成此操作。
方法：
1.循环遍历bars数组的索引。
2.对于每个栏, 我们可以执行以下操作：

• 当栈不为空并且当前栏的高度大于栈的顶部栏时,
• 将顶栏索引存储在pop_height并从栈中弹出。
• 查找弹出的条的左条(当前顶部)与当前条之间的距离。
• 找到顶部栏和当前栏之间的最小高度。
• 可以捕获的最大水量是距离* min_height.
• 包括弹出条在内的被困水是(距离* min_height)–高度[pop_height].
• 将其添加到ans

3.最终答案将是ans.
C++

//C++ implementation of the approach #include < bits/stdc++.h> using namespace std; //Function to return the maximum //water that can be stored int maxWater( int height[], int n) {//Stores the indices of the bars stack < int> st; //Stores the final result int ans = 0; //Loop through the each bar for ( int i = 0; i < n; i++) {//Remove bars from the stack //until the condition holds while ((!st.empty()) & & (height[st.top()] < height[i])) {//Store the height of the top //and pop it. int pop_height = height[st.top()]; st.pop(); //If the stack does not have any //bars or the the popped bar //has no left boundary if (st.empty()) break ; //Get the distance between the //left and right boundary of //popped bar int distance = i - st.top() - 1; //Calculate the min. height int min_height = min(height[st.top()], height[i]) - pop_height; ans += distance * min_height; }//If the stack is either empty or //height of the current bar is less than //or equal to the top bar of stack st.push(i); } return ans; }//Driver code int main() {int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; int n = sizeof (arr) /sizeof (arr[0]); cout < < maxWater(arr, n); return 0; }//The code is contributed by Soumitri Chattopadhyay

Java

import java.util.*; import java.io.*; //Java implementation of the approach class GFG {//Function to return the maximum //water that can be stored public static int maxWater( int [] height) { //Stores the indices of the bars Stack< Integer> stack = new Stack< > (); //size of the array int n = height.length; //Stores the final result int ans = 0 ; //Loop through the each bar for ( int i = 0 ; i < n; i++) {//Remove bars from the stack //until the condition holds while ((!stack.isEmpty()) & & (height[stack.peek()] < height[i])) {//store the height of the top //and pop it. int pop_height = height[stack.peek()]; stack.pop(); //If the stack does not have any //bars or the the popped bar //has no left boundary if (stack.isEmpty()) break ; //Get the distance between the //left and right boundary of //popped bar int distance = i - stack.peek() - 1 ; //Calculate the min. height int min_height = Math.min(height[stack.peek()], height[i]) - pop_height; ans += distance * min_height; }//If the stack is either empty or //height of the current bar is less than //or equal to the top bar of stack stack.push(i); }return ans; } //Driver code public static void main(String[] args) { int arr[] = { 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 }; System.out.print(maxWater(arr)); } }

输出如下：

6

时间复杂度：O(n)
辅助空间：O(n)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  电脑清灰一般多少钱啊详细介绍
• 

  2021年春分适不适合安葬
• 

  你只看到了被低估的京东股价，却没看到京东重注技术的长期价值
• 

  除夕夜必须是在大年三十吗
• 

  尤尼有什么好的羽毛球拍推荐一下？
• 

  三国志14郭嘉亲密关系有哪些 三国志14郭嘉亲密好友一览
• 

  美的安装空调需要报备么,先检测下这些地方
• 

  虾和桃子吃了肚子疼怎么办
• 

  二十不惑大宝大熊分手了吗
• 

  5变异阵容怎么玩 5变异阵容玩法
• 

  在刑诉里拘传前是必须先传唤吗
• 

  明日方舟干员号角技能分析 号角专精哪个技能
• 

  要求开发票对电商有什么区别
• 

  农村房产怎么公证 如何公证农村房产
• 

  消防维保要什么上岗证 消防维保人员需要什么证件
• 

  Win7如何修复exe文件关联错误？
• 

  风油精放在房间可以驱蚊吗
• 

  雨热同期什么意思 什么叫雨热同期
• 

  椰子肉怎么看熟了没，椰子怎么知道熟了
• 

  西安市儿童医院|陕西省第一个省级儿科重点实验室落户西安市儿童医院

• C语言编程面试常见问题介绍S1
• Trie插入和搜索实现原理和代码实现
• JP Morgan Chase＆Co面试经历|S3（实习）
• 算法设计（最大滑动窗口-大小为k的所有子数组的最大值 S2）
• 机器学习中的聚类是什么（如何理解？）
• 如何使用Google Colab（详细步骤图解）
• Python中的手写方程式求解器详细实现
• python开发的常见问题S12（列表和元组）
• 三星（SRIB）实习面试经验