fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int trap(vector<int>& height) {
  7.     if (height.empty()) return 0;
  8.  
  9.     int left = 0, right = height.size() - 1;
  10.     int max_left = 0, max_right = 0;
  11.     int water_trapped = 0;
  12.  
  13.     while (left <= right) {
  14.         if (height[left] <= height[right]) {
  15.             if (height[left] > max_left)
  16.                 max_left = height[left];
  17.             else
  18.                 water_trapped += max_left - height[left];
  19.             left++;
  20.         } else {
  21.             if (height[right] > max_right)
  22.                 max_right = height[right];
  23.             else
  24.                 water_trapped += max_right - height[right];
  25.             right--;
  26.         }
  27.     }
  28.  
  29.     return water_trapped;
  30. }
  31.  
  32. int main() {
  33.     vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
  34.     cout << trap(height) << endl; // Output: 6
  35.     return 0;
  36. }
  37.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
6
https://ideone.com/tez7Uk
language:
C++14 (gcc 8.3)
created:
15 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!