fork download
copy 
  1. //trapped rainwater problem with Stack
  2.  
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. class Main {
  7.     public static void main(String[] args)throws IOException {
  8.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  9.         int n=Integer.parseInt(br.readLine());
  10.         int[] arr=new int[n];
  11.         for(int i=0;i<n;i++){
  12.             arr[i]=Integer.parseInt(br.readLine());
  13.         }
  14.         int total=0;
  15.         Stack<Integer> st=new Stack<>();
  16.         for(int i=0;i<n;i++){
  17.  
  18.             while(!st.isEmpty()&&arr[st.peek()]<arr[i]){
  19.                 int pop_height=arr[st.pop()];
  20.                 if(st.isEmpty()) break;
  21.                 int distance=i-st.peek()-1;
  22.                 int height=Math.min(arr[st.peek()],arr[i]);
  23.                 int water=(height-pop_height)*distance;
  24.                 total+=water;
  25.  
  26.             }
  27.             st.push(i);
  28.         }
  29.         System.out.println(total);
  30.     }
  31. }
Success #stdin #stdout 0.11s 55008KB
comments (?)
stdin
copy 
7
3
0
1
0
4
0
2
stdout
copy 
10
https://ideone.com/LQuPkO
language:
Java (HotSpot 12)
created:
2 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!