一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 375|回复: 1
收起左侧

[算法题] Trapping Rain Water 求助

[复制链接] |试试Instant~ |关注本帖
jy_121 发表于 2015-9-3 23:05:19 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目链接如下,要求求所能接收的最大雨水面积,自己想了一个方法,和答案不一样,但是到第七个case就过不了了:

http://www.lintcode.com/en/problem/trapping-rain-water/


大概就是只在后一个柱体比前一个高时才进行累加,并且更新高度,程序如下:
  1. public int trapRainWater(int[] heights) {
  2.         // write your code here
  3.       if(heights.length == 0 || heights.length == 1){
  4.             return 0;
  5.         }
  6.         
  7.                 int start = 0;
  8.                 int end = heights.length - 1;
  9.                 int v1 = heights[start];
  10.                 int v2 = heights[end];
  11.                 int s1 = 0;
  12.                 int s2 = 0;
  13.                
  14.                 while(start < end){
  15.                         while(heights[start] <= v1 && start < end){
  16.                                 s1 = s1 + v1 - heights[start];
  17.                                 start++;       
  18.                         }
  19.                         while(heights[end] <= v2 && start < end){
  20.                                 s2 = s2 + v2 - heights[end];
  21.                                 end--;       
  22.                         }
  23.                         v1 = heights[start];
  24.                         v2 = heights[end];
  25.                 }
  26.                 return s1 + s2;
  27.     }
复制代码
谢谢!


question.png
 楼主| jy_121 发表于 2015-9-4 09:55:48 | 显示全部楼层
已经得到了一位同学的解答。

start,end两个指针向中间移动的时候只考虑了两边的边界情况,没有考虑中间的情况,v1和v2只能取两者中小的那个 v1 = heights[start]; v2 = heights[end]; 应该改为 v1 = Math.min(heights[start],heights[end]); v2 = v1;
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表