fork download 
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. int trap(std::vector<int>& height) {
  5.     int n = height.size();
  6.     if (n == 0) return 0;
  7.  
  8.     int left = 0, right = n - 1;
  9.     int left_max = 0, right_max = 0;
  10.     int water = 0;
  11.  
  12.     while (left < right) {
  13.         if (height[left] <= height[right]) {
  14.             if (height[left] >= left_max) {
  15.                 left_max = height[left];
  16.             } else {
  17.                 water += left_max - height[left];
  18.             }
  19.             left++;
  20.         } else {
  21.             if (height[right] >= right_max) {
  22.                 right_max = height[right];
  23.             } else {
  24.                 water += right_max - height[right];
  25.             }
  26.             right--;
  27.         }
  28.     }
  29.  
  30.     return water;
  31. }
  32.  
  33. int main() {
  34.     std::vector<int> height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
  35.     std::cout << "Output for Example 1: " << trap(height1) << std::endl;
  36.  
  37.     std::vector<int> height2 = {4,2,0,3,2,5};
  38.     std::cout << "Output for Example 2: " << trap(height2) << std::endl;
  39.  
  40.     return 0;
  41. }
  42.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Output for Example 1: 6
Output for Example 2: 9
https://ideone.com/TTKb27
language:
C++ (gcc 8.3)
created:
13 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!