本文共 3055 字,大约阅读时间需要 10 分钟。
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.
给出n个非负整数,表示一个立面图,每一个条形图的宽度是1,计算下雨之后这个条形图能够存多少水
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
上面那个立面图是用一组数组[0,1,0,2,1,0,1,3,2,1,2,1].在这个情况下,6个单元的雨水被填满。
#include#include int trap(int *height,int heightSize);int main(){ //今日份leetcode int p[] = { 0,1,0,2,1,0,1,3,2,1,2,1}; printf("%d \n",trap(p,12)); return 0;}int trap(int *height, int heightSize){ int container = 0; //表示该条件下雨水的体积 int start = 0; //间距扫描的开始端 int end = 1; //间距扫描的结束端 int obstacle = 0; //计算障碍物的体积 int maxIndex = 0; //判定直接返回0的情况 if(heightSize < 3) { return 0; } //找到最高墙,防止侧漏 for(int i = 0 ;i < heightSize;i++) { if(height[i] > height[maxIndex]) { maxIndex = i; } } //从最高墙的左侧开始遍历 while(start <= maxIndex && end <= maxIndex) { if(height[start] > height[end]) { obstacle += height[end]; } else { container = container + height[start] * (end - start - 1) - obstacle; obstacle = 0; start = end; } end ++; } start = heightSize - 1,end = start - 1,obstacle = 0; //从最高墙的右侧开始遍历 while(start >= maxIndex && end >= maxIndex) { if(height[start] > height[end]) { obstacle += height[end]; } else { container = container + height[start] * (start - end - 1) - obstacle; obstacle = 0; start = end; } end --; } return container;}
int trap(vector & height){ if(height == null) return 0; int ans = 0; int size = height.size(); vector left_max(size), right_max(size); left_max[0] = height[0]; for (int i = 1; i < size; i++) { left_max[i] = max(height[i], left_max[i - 1]); } 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]); } for (int i = 1; i < size - 1; i++) { ans += min(left_max[i], right_max[i]) - height[i]; } return ans;}
转载地址:http://xggpb.baihongyu.com/