fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. class Solution {
  6. public:
  7.     int trap(std::vector<int>& height) {
  8.         int i = 0, left_max = height[0], sum = 0;
  9.         int j = height.size() - 1, right_max = height[j];
  10.         while (i < j) {
  11.             if (left_max <= right_max) {
  12.                 sum += (left_max - height[i]);
  13.                 i++;
  14.                 left_max = std::max(left_max, height[i]);
  15.             } else {
  16.                 sum += (right_max - height[j]);
  17.                 j--;
  18.                 right_max = std::max(right_max, height[j]);
  19.             }
  20.         }
  21.         return sum;
  22.     }
  23. };
  24.  
  25. int main() {
  26.     std::vector<int> height = {4,2,0,3,2,5};
  27.     Solution obj;
  28.     int trappedWater = obj.trap(height);
  29.     std::cout << "Trapped water: " << trappedWater << std::endl;
  30.     return 0;
  31. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
Trapped water: 9
https://ideone.com/mYvFTj
language:
C++14 (gcc 8.3)
created:
14 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!