Trapping Rain Water | C ++ implementation of the approach ; Function to return the maximum water that can be stored ; Stores the indices of the bars ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxWater ( int height [ ] , int n ) { stack < int > st ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { while ( ( ! st . empty ( ) ) && ( height [ st . top ( ) ] < height [ i ] ) ) { int pop_height = height [ st . top ( ) ] ; st . pop ( ) ; if ( st . empty ( ) ) break ; int distance = i - st . top ( ) - 1 ; int min_height = min ( height [ st . top ( ) ] , height [ i ] ) - pop_height ; ans += distance * min_height ; } st . push ( i ) ; } return ans ; } 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 ; }