fork download
copy 
  1. #include <cassert>
  2. #include <stack>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int trap_rain_water(const vector<int> &h) {
  7.   int sum = 0;
  8.  
  9.   stack<int> last_seen_level_at;
  10.   int last_i = 0;
  11.   for (int col = 0; col < h.size(); ++col) {
  12.     int i = h[col];
  13.  
  14.     if (i > last_i) {
  15.       // flush prev levels below
  16.       for (auto k = i; k > last_i; --k) {
  17.         if (!last_seen_level_at.empty()) {
  18.           sum += (col - last_seen_level_at.top());
  19.           last_seen_level_at.pop();
  20.         }
  21.       }
  22.     }
  23.  
  24.     if (i < last_i) {
  25.       // track start col of levels
  26.       for (auto k = last_i; k > i; --k) {
  27.         last_seen_level_at.push(col);
  28.       }
  29.     }
  30.  
  31.     last_i = i;
  32.   }
  33.   return sum;
  34. }
  35.  
  36. int main() {
  37.   // www.youtube.com/watch?v=HmBbcDiJapY&t=333s
  38.   vector<int> h = {1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
  39.   int result = 1 + 1 + 2 + 1 + 1;
  40.  
  41.   assert(trap_rain_water(h) == result);
  42.   return 0;
  43. }
  44.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Gl4hAp
language:
C++14 (gcc 8.3)
created:
6 years 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!