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

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

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

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][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 个单位的雨水（蓝色部分表示雨水）。

示例:

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

来源：力扣（LeetCode）

--------------------

### java实现方法1：  ###

/**
         * 装多少水
         *
         * @param height 数组
         * @return 多少水
         */
        private int trappingRainWater(int[] height) {
            if (height == null || height.length < 3) {
                return 0;
            }
            int result = 0;
            int size = height.length;
            for (int i = 0; i < size; i++) {
                int maxLeft = 0;
                int maxRight = 0;
                for (int j = i; j >= 0; j--) {
                    maxLeft = Math.max(maxLeft, height[j]);
                }
                for (int j = i; j < size; j++) {
                    maxRight = Math.max(maxRight, height[j]);
                }
                result += Math.min(maxLeft, maxRight) - height[i];
            }
            return result;
        }

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

空间复杂度：O(1)

--------------------

### python实现方法1： ###

from typing import List
    
    
    def trapping_rain_water(arr: List[int]) -> int:
        '''
            能装多少水
        Args:
            arr:数组
        Returns:
            装的水
        '''
        if arr is None or len(arr) < 3:
            return 0
        result = 0
        size = len(arr)
        for i in range(size - 1):
            max_left = 0
            max_right = 0
            j = i
            while j >= 0:
                max_left = max(max_left, arr[j])
                j -= 1
            k = i
            while k < size:
                max_right = max(max_right, arr[k])
                k += 1
            result += min(max_left, max_right) - arr[i]
        return result

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

空间复杂度：O(1)

--------------------

### java实现方法2： ###

/**
         * 装多少水
         *
         * @param height 数组
         * @return 多少水
         */
        private int trappingRainWater2(int[] height) {
            if (height == null || height.length < 3) {
                return 0;
            }
            int result = 0;
            int left = 0;
            int right = height.length - 1;
            int leftMax = 0;
            int rightMax = 0;
            while (left < right) {
                if (height[left] < height[right]) {
                    leftMax = Math.max(leftMax, height[left]);
                    result += (leftMax - height[left]);
                    left++;
                } else {
                    rightMax = Math.max(rightMax, height[right]);
                    result += (rightMax - height[right]);
                    right--;
                }
            }
            return result;
        }

时间复杂度:O(n)

空间复杂度:O(1)

--------------------

### python实现方法2： ###

def trapping_rain_water2(self, height: List[int]) -> int:
            '''
                能装多少水
            Args:
                height:数组
            Returns:
                装的水
            '''
            if not height or len(height) < 3:
                return 0
            left_max, right_max = 0, 0
            left, right = 0, len(height) - 1
            result = 0
            while left < right:
                if height[left] < height[right]:
                    left_max = max(left_max, height[left])
                    result += (left_max - height[left])
                    left += 1
                else:
                    right_max = max(right_max, height[right])
                    result += (right_max - height[right])
                    right -= 1
            return result

时间复杂度: O(n)

空间复杂度: O(1)

--------------------

### 源码地址： ###

https://github.com/zhangyu345293721/leetcode

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201