今天写了一道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,大大减少了程序的运行时间。
得到预期的结果也许不难,但是能够将所有的情况考虑周全却不容易。即使得到了正确结果,很多时候,不妨先别着急庆祝,看看是否有值得优化的地方,多一些思考,多一些实践,自己的进步将会十分明显!!!
网友评论