trap_water.cxx

#include<iostream>
#include<vector>

int trap_water(std::vector<int> &v){
  int water = 0;
  int h = 0;

  //== Find Max Height Bar
  size_t imax = 0; 
  for( size_t i=1;i<v.size();i++ )
    if( v[imax] < v[i] ) imax = i;
  
  //== left -> imax
  h=0;
  for( size_t i=0;i<imax;i++ )
    if( v[i] > h ) h = v[i];
    else water += h-v[i];
  //== right -> imax
  h=0;
  for( size_t i=v.size()-1;i>imax;i-- )
    if( v[i] > h ) h = v[i];
    else water += h-v[i];
  //== Done!
  return water;
}

using namespace std;
int main(){
  vector<int> v;
  v = {2, 0, 2};
  cout<<trap_water(v)<<endl;
  v = {3, 0, 0, 2, 0, 4};
  cout<<trap_water(v)<<endl;
  v = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
  cout<<trap_water(v)<<endl;
  return 0;
}