设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › 数据结构与算法 › leetcode 42. Trapping Rain Water 谷歌面试题
返回列表 发新帖
查看: 1986|回复: 0

[学习笔记] leetcode 42. Trapping Rain Water 谷歌面试题

[复制链接]
Seawolf
发表于 2019-8-18 13:01:01 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 Seawolf 于 2019-8-19 06:47 编辑
  1. 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.


  4. 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.

  6. Example:

  8. Input: [0,1,0,2,1,0,1,3,2,1,2,1]
  9. Output: 6
复制代码


rainwatertrap.png

  1. class Solution {
  2.    
  3.     public static int trap(int[] height) {
  4.            
  5.             if(height == null || height.length == 0) {
  6.                    
  7.                     return 0;
  8.                    
  9.             }
  10.            
  11.             int count = 0;
  12.            
  13.             generateNum(height, count);
  14.            
  15.             return count;
  16.         
  17.     }
  18.    
  19.     public static void generateNum(int[] height, int count) {
  20.         
  21.             int len = height.length;
  22.            
  23.             int start = 0,end = 0;
  24.            
  25.             while(start != len && end != len) {
  26.            
  27.             while(height[start] == 0) {
  28.                    
  29.                     start++;
  30.             }
  31.                
  32.                 end = start;
  33.                
  34.                 end ++;
  35.             
  36.                 while(height[start] != 1) {
  37.                        
  38.                         start++;
  39.                 }
  40.                                
  41.                 if(start>0) {
  42.                        
  43.                         while(end < len && height[end] == 0) {
  44.                                
  45.                                 if(end == len -1 && height[end] != 1) {
  46.                                        
  47.                                         end = start;
  48.                                        
  49.                                 }
  50.                                
  51.                                 end++;
  52.                        
  53.                         }
  54.                        
  55.                 if(end - start >1) {
  56.                                
  57.                         count = count + end - start - 1;

  59.                         }
  60.                        
  61.                 }
  62.                
  63.                 while(end < len && height[end] != 1) {
  64.                        
  65.                         end++;
  66.                 }
  67.                
  68.                 start = end;
  69.                
  70.                 todo = false;
  71.                
  72.             }
  73.            
  74.             int ass = 0;
  75.            
  76.             if(start >= len-1 && end >= len-1) {
  77.                    
  78.                     for(int i = 0; i< len; i++) {
  79.                            
  80.                         if(height[i] != 0) {
  81.                                
  82.                                 ass = ass+ 1;
  83.                                
  84.                                 height[i] = height[i] - 1;
  85.                         }
  86.                     }
  87.                    
  88.                     if(ass == 1) {
  89.                            
  90.                             return;
  91.                     }
  92.                     else {
  93.                            
  94.                             ass = 0;
  95.                     }
  96.                    
  97.                     generateNum(height,count);
  98.                    
  99.             }
  100.     }
  101. }
复制代码



上面这个code虽然可以算出所有的结果，但是交给leetcode 去执行，会报run out of time error 也就是说 efficiency 太差了

下面尝试暴力解法

  1. class Solution {
  2.    
  3.     public static int trap(int[] height) {
  4.         
  5.         int len = height.length;
  6.         
  7.         if(len == 0){
  8.             
  9.             return 0;
  10.         }
  11.         
  12.         int ans = 0;
  13.         
  14.         for(int i = 1 ; i < len-1 ; i++){
  15.             
  16.             int leftMax = 0, rightMax = 0;
  17.             
  18.             for(int j = i; j >= 0; j--){
  19.                
  20.                 leftMax = Math.max(leftMax, height[j]);
  21.                
  22.             }
  23.             
  24.             for(int m = i  ; m < len; m ++){
  25.                
  26.                 rightMax = Math.max(rightMax,height[m]);
  27.                   
  28.             }
  29.             

  31.             ans = ans + Math.min(leftMax,rightMax) - height[i];
  32.                
  33.             
  34.             
  35.         }
  36.         
  37.         return ans;
  38.         
  39.     }
  40. }
复制代码


19.jpg

虽然通过了pass，但是效率依然是很低，继续改进代码。


  1. class Solution {
  2.    
  3.     public static int trap(int[] height) {
  4.         
  5.         int len = height.length;
  6.         
  7.         if(len == 0){
  8.             
  9.             return 0;
  10.         }
  11.         
  12.         int ans = 0;
  13.         
  14.         int[] leftMax = new int[len];
  15.         
  16.         int[] rightMax = new int[len];
  17.         
  18.         leftMax[0] = height[0];
  19.         
  20.         for(int i = 1 ;i <len ; i++ ){
  21.             
  22.             leftMax[i] = Math.max(height[i], leftMax[i-1]);
  23.         }
  24.         
  25.         rightMax[len-1] = height[len - 1];
  26.         
  27.         for(int i = len -2 ;i >=0 ; i-- ){
  28.             
  29.             rightMax[i] = Math.max(height[i], rightMax[i+1]);
  30.         }
  31.         
  32.         for(int i = 0 ;i< len ; i++ ){
  33.             
  34.             ans = ans + Math.min(rightMax[i], leftMax[i]) - height[i];
  35.         }
  36.         
  37.         return ans;
  38.         
  39.     }
  40. }
复制代码


20.jpg

running time 由 O(N^2) 提高到O(N), 继续优化代码，使用双指针进行优化

how it works?

1.jpg

2.jpg

3.jpg

4.jpg

5.jpg

6.jpg

7.jpg

8.jpg

9.jpg

10.jpg

11.jpg


  1. class Solution {
  2.    
  3.     public static int trap(int[] height) {
  4.         
  5.         int ans = 0;
  6.         
  7.         int left_max = 0,right_max = 0;
  8.         
  9.         int left = 0,right = height.length- 1;
  10.         
  11.         while(left < right){
  12.             
  13.             if(height[left] < height[right]){
  14.                
  15.                 if(height[left] >= left_max)
  16.                     left_max = height[left];
  17.                 else
  18.                     ans = ans + left_max - height[left];
  19.                
  20.                 left++;
  21.             }
  22.             
  23.             else{
  24.                
  25.                 if(height[right] >= right_max)
  26.                     right_max = height[right];
  27.                 else
  28.                     ans = ans + right_max - height[right];
  29.                
  30.                 right--;
  31.             }
  32.         }
  33.         
  34.         return ans;
  35.         
  36.     }
  37. }
复制代码


21.jpg

介绍另外一种方法，使用stack 栈来操作。

  1. class Solution {
  2.    
  3.     public static int trap(int[] height) {
  4.         
  5.         int ans = 0;
  6.         
  7.         int current = 0;
  8.         
  9.         int len = height.length;
  10.         
  11.         Stack <Integer> stack = new Stack<>();
  12.         
  13.         while(current < len){
  14.             
  15.             while(!stack.empty()  && height[current] > height[stack.peek()]){
  16.                
  17.                 int top = stack.peek();
  18.                
  19.                 stack.pop();
  20.                
  21.                 if(stack.empty()){
  22.                     
  23.                     break;
  24.                 }
  25.                
  26.                 int distance = current - stack.peek() -1 ;
  27.                
  28.                 int bounded = Math.min(height[current], height[stack.peek()]) - height[top];
  29.                
  30.                 ans = ans + distance * bounded;
  31.             }
  32.             
  33.             stack.push(current++);
  34.         }
  35.         
  36.         return ans;
  37.         
  38.     }
  39. }
复制代码


nice job！！

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +3 收起 理由
糖逗 + 5 + 5 + 3

查看全部评分

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-8 17:22

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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