Trapping Rain Water |  ; Java implementation of the approach ; Function to return the maximum water that can be stored ; Stores the indices of the bars ; size of the array ; Stores the final result ; Loop through the each bar ; Remove bars from the stack until the condition holds ; store the height of the top and pop it . ; If the stack does not have any bars or the the popped bar has no left boundary ; Get the distance between the left and right boundary of popped bar ; Calculate the 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 ; Driver code
import java . util . * ; import java . io . * ; class GFG { public static int maxWater ( int [ ] height ) { Stack < Integer > stack = new Stack < > ( ) ; int n = height . length ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { while ( ( ! stack . isEmpty ( ) ) && ( height [ stack . peek ( ) ] < height [ i ] ) ) { int pop_height = height [ stack . peek ( ) ] ; stack . pop ( ) ; if ( stack . isEmpty ( ) ) break ; int distance = i - stack . peek ( ) - 1 ; int min_height = Math . min ( height [ stack . peek ( ) ] , height [ i ] ) - pop_height ; ans += distance * min_height ; } stack . push ( i ) ; } return ans ; } 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 ) ) ; } }