题目描述
单调栈
样例
use std::cmp;
impl Solution {
pub fn trap(height: Vec<i32>) -> i32 {
let mut left = vec![0; height.len()];
let mut right = vec![0; height.len()];
let mut stack = Vec::<usize>::new();
for i in 0..height.len() {
if(stack.is_empty() || height[i]>= height[*stack.last().unwrap()]){
left[i] = -1;
stack.push(i);
}else {
//println!("{:?}", *stack.last().unwrap() as i32);
left[i] = *stack.last().unwrap() as i32;
}
}
stack.clear();
for i in (0..height.len()).rev() {
if(stack.is_empty() || height[i] >= height[*stack.last().unwrap()]){
right[i] = -1;
stack.push(i);
}else {
//println!("{:?}", *stack.last().unwrap() as i32);
right[i] = *stack.last().unwrap() as i32;
}
}
let mut trapped_water = 0;
for i in 0..height.len(){
let (l, r) = (left[i], right[i]);
if l == -1 || r == -1 {
continue;
}
//println!("{:?}, {:?}, {:?}", i, l , r);
trapped_water += (cmp::min(height[l as usize], height[r as usize])-height[i]);
}
trapped_water
}
}