AcWing 1574. 接雨水 java 单调栈
原题链接
简单
作者:
henhen敲
,
2020-05-28 00:13:17
,
所有人可见
,
阅读 1016
public static void main(String[] args)throws Exception{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] h = new int[n];
int[] m = new int[n];
int[] s = new int[n+1];//前缀和
for(int i=0; i<n; i++){
h[i] = in.nextInt();
s[i+1] = s[i] + h[i];
}
Stack<Integer> st = new Stack<>();//单调栈
for(int i=n-1; i>=0; i--){
int x = h[i];
int t = i;
while(st.size()>0&&x>h[st.peek()]) t = st.pop();
m[i] = st.size()==0?t:st.peek();
st.push(i);
}
int cur = 0;
int sum = 0;
while(cur<n-1){
int r = h[m[cur]];
int l = h[cur];
sum += m[cur]-cur<0? 0:(m[cur]-cur-1)*Math.min(r, l) - (s[m[cur]]-s[cur+1]) ;
cur = m[cur];
}
System.out.print(sum);
}