题目描述
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Example1:
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
解题思路
-
class Solution { public: int trap(vector<int>& height) { int size = height.size(); if(size == 0){ return 0; } vector<int> left_max(size, 0); left_max[0] = height[0]; for(int i = 1; i < size; i++){ left_max[i] = max(height[i], left_max[i - 1]); } vector<int> right_max(size, 0); right_max[size - 1] = height[size - 1]; for(int i = size - 2; i >= 0; i--){ right_max[i] = max(height[i], right_max[i + 1]); } int res = 0; for(int i = 1; i < size - 1; i++){ res += min(left_max[i], right_max[i]) - height[i]; } return res; } };
