谈一道LeetCode——接雨水
今天写了一道LeetCode，虽然题目并不难，但是过程没有想象中那样简单，经历了一波三折，有什么曲折呢，一起来看看吧！
题目介绍
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
图片.png
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
题目分析
由题意和图可知，此题说通俗一点就是计算矩形的面积。
简单来说就是，一层层地计算这一层的矩形面积，在计算本层的时候，应该注意没有方块以及之前被覆盖的矩形区域。
比如说，高度为1的矩形被统计过后，下一次统计时，第一层即使是空的，也不能被纳入该次计算中。
解题
本人写了第一份程序，测试了一些样例后，没有问题，提交了。
下面展示下程序，鉴于本人代码水平不高，还请各位大佬多多指教......
class Solution {
public:
int trap(vector<int>& height) {
int area=0;
int temp=0;
if(height.size()==0){
return 0;
}else{
int max=0,max_index=0;
for(int i=0;i<height.size();i++){
if(height[i]>max){
max=height[i];
max_index=i;
}
}
for(int i=1;i<=max;i++){
int start=find_start(height,i);
int end=find_end(height,i);
if(start!=-1&&end!=-1){
for(int j=start;j<=end;j++){
if(i>=height[j]){
if(height[j]>temp){
area+=(i-height[j]);
}else{
area+=(i-temp);
}
}
}
temp=i;
}
}
return area;
}
}
int find_end(vector<int>& height,int num){
int locate=-1;
for(int i=height.size()-1;i>=0;i--){
if(height[i]>=num){
locate=i;
break;
}
}
return locate;
}
int find_start(vector<int>& height,int num){
int locate=-1;
for(int i=0;i<height.size();i++){
if(height[i]>=num){
locate=i;
break;
}
}
return locate;
}
};
测试了很多样例，都通过了，但是系统却未通过。一看原因，如下图
图片.png
很简单，最后一个样例太大了，导致程序在这个样例上超时了。
再回到程序中，发现有些循环并非需要这样写，可优化的地方很多
基于此，重新写了一份，这次通过了，下面展示下程序
class Solution {
public:
int trap(vector<int>& height) {
int area=0;
int length=height.size();
int max_l=0,max_r=0;
if(length==0){
return 0;
}else{
for(int i=1;i<length-1;i++){
max_l=0,max_r=0;
for(int j=i;j>=0;j--){
max_l=max_l>height[j]?max_l:height[j];
}
for(int j=i;j<length;j++){
max_r=max_r>height[j]?max_r:height[j];
}
area+=(max_l<max_r?max_l:max_r)-height[i];
}
return area;
}
}
};
这次倒是成功通过了，结果如下：
图片.png
但是发现时间方面还是有很大优化的空间，分析上述程序可以发现
for(int i=1;i<length-1;i++){
/*
*
*/
}
这个循环里面两个找左右最大小值时，两个循环每次都会被执行，实际上，我们完全可以设置两个vector预先将左边和右边的最大值提前存储起来，也许会多花一些空间，但是时间消耗会明显减少。
下面展示改进后的程序：
class Solution {
public:
int trap(vector<int>& height) {
int length=height.size();
if(length==0){
return 0;
}else{
int area=0;
int temp=0;
vector<int> max_start(length),max_end(length);
max_start[0]=height[0];
max_end[length-1]=height[length-1];
for(int i=1;i<length;i++){
max_start[i]=max_start[i-1]>height[i]?max_start[i-1]:height[i];
}
for(int i=length-2;i>=0;i--){
max_end[i]=max_end[i+1]>height[i]?max_end[i+1]:height[i];
}
for(int i=1;i<length-1;i++){
temp=max_start[i]<max_end[i]?max_start[i]:max_end[i];
area+=temp-height[i];
}
return area;
}
}
};
提交结果如下图所示：
图片.png
效果显著！！！
总结
虽然此题并不难，但是仔细去品味还是有不少可以推敲的。
从一开始得出正确答案，而面对大样例时，会超时。
之后进行改进，去掉了一些不必要的循环，通过，但是耗时多。
最后，从空间角度出发，开辟两个vector，大大减少了程序的运行时间。
得到预期的结果也许不难，但是能够将所有的情况考虑周全却不容易。即使得到了正确结果，很多时候，不妨先别着急庆祝，看看是否有值得优化的地方，多一些思考，多一些实践，自己的进步将会十分明显！！！
