LeetCode：42. Trapping Rain Water（能装多少水问题）

青旅半醒 2022-04-03 09:58 214阅读 0赞

文章最前： 我是Octopus，这个名字来源于我的中文名—章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

相关文章：

  1. LeetCode：55. Jump Game（跳远比赛）
  2. Leetcode：300. Longest Increasing Subsequence（最大增长序列）
  3. LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）

目录结构：

题目描述：

java实现方法1：

python实现方法1：

java实现方法2：

python实现方法2：

源码地址：

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:

  1. 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
  2. 输出: 6

来源：力扣（LeetCode）

java实现方法1：

  1. /**
  2.      * 装多少水
  3.      *
  4.      * @param height 数组
  5.      * @return 多少水
  6.      */
  7.     private int trappingRainWater(int[] height) {
  8.         if (height == null || height.length < 3) {
  9.             return 0;
  10.         }
  11.         int result = 0;
  12.         int size = height.length;
  13.         for (int i = 0; i < size; i++) {
  14.             int maxLeft = 0;
  15.             int maxRight = 0;
  16.             for (int j = i; j >= 0; j--) {
  17.                 maxLeft = Math.max(maxLeft, height[j]);
  18.             }
  19.             for (int j = i; j < size; j++) {
  20.                 maxRight = Math.max(maxRight, height[j]);
  21.             }
  22.             result += Math.min(maxLeft, maxRight) - height[i];
  23.         }
  24.         return result;
  25.     }

时间复杂度：O(n^2)

空间复杂度：O(1)

python实现方法1：

  1. from typing import List
  4. def trapping_rain_water(arr: List[int]) -> int:
  5.     '''
  6.         能装多少水
  7.     Args:
  8.         arr:数组
  9.     Returns:
  10.         装的水
  11.     '''
  12.     if arr is None or len(arr) < 3:
  13.         return 0
  14.     result = 0
  15.     size = len(arr)
  16.     for i in range(size - 1):
  17.         max_left = 0
  18.         max_right = 0
  19.         j = i
  20.         while j >= 0:
  21.             max_left = max(max_left, arr[j])
  22.             j -= 1
  23.         k = i
  24.         while k < size:
  25.             max_right = max(max_right, arr[k])
  26.             k += 1
  27.         result += min(max_left, max_right) - arr[i]
  28.     return result

时间复杂度：O(n^2)

空间复杂度：O(1)

java实现方法2：

  1. /**
  2.      * 装多少水
  3.      *
  4.      * @param height 数组
  5.      * @return 多少水
  6.      */
  7.     private int trappingRainWater2(int[] height) {
  8.         if (height == null || height.length < 3) {
  9.             return 0;
  10.         }
  11.         int result = 0;
  12.         int left = 0;
  13.         int right = height.length - 1;
  14.         int leftMax = 0;
  15.         int rightMax = 0;
  16.         while (left < right) {
  17.             if (height[left] < height[right]) {
  18.                 leftMax = Math.max(leftMax, height[left]);
  19.                 result += (leftMax - height[left]);
  20.                 left++;
  21.             } else {
  22.                 rightMax = Math.max(rightMax, height[right]);
  23.                 result += (rightMax - height[right]);
  24.                 right--;
  25.             }
  26.         }
  27.         return result;
  28.     }

时间复杂度:O(n)

空间复杂度:O(1)

python实现方法2：

  1. def trapping_rain_water2(self, height: List[int]) -> int:
  2.         '''
  3.             能装多少水
  4.         Args:
  5.             height:数组
  6.         Returns:
  7.             装的水
  8.         '''
  9.         if not height or len(height) < 3:
  10.             return 0
  11.         left_max, right_max = 0, 0
  12.         left, right = 0, len(height) - 1
  13.         result = 0
  14.         while left < right:
  15.             if height[left] < height[right]:
  16.                 left_max = max(left_max, height[left])
  17.                 result += (left_max - height[left])
  18.                 left += 1
  19.             else:
  20.                 right_max = max(right_max, height[right])
  21.                 result += (right_max - height[right])
  22.                 right -= 1
  23.         return result

时间复杂度: O(n)

空间复杂度: O(1)

源码地址：

  1.      https://github.com/zhangyu345293721/leetcode

发表评论

表情：
评论列表 （有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读