leetcode:42.接雨水

42. 接雨水

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/trapping-rain-water

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

示例 1：

输入：height = [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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= $2\ast 10^4$
• 0 <= height[i] <= $10^5$

解法

• 暴力算法：左右两边高度的最小值，
  

• 动态规划：空间换时间，先从左到右遍历获取左边柱子的最大值列表，从右往左遍历获取右边柱子的最大值列表，这样每次遍历柱子的时候其左右高度柱子直接从列表中取出即可
  

• 单调栈：构建一个从大到小依次递减的栈，如果准备入栈的元素比栈顶元素还大，说明形成低洼，将该栈顶元素pop出，其左边最高点即为栈顶元素，右边最高点为待入栈元素，这里pop之后注意判空；
  
  
  
  

• 双指针：
  
  

代码实现

暴力算法

python实现

class Solution:
    def trap(self, height: List[int]) -> int:
        # 暴力算法，找左右两边柱子的边界，然后计算
        n = len(height)
        if n < 3:
            return 0
        
        ans = 0
        for i in range(0, n-1):
            max_left, max_right = 0, 0
            # find left max height
            for j in range(i):
                if height[j] > height[i]:
                    max_left = max(max_left, height[j])
            
            # find right max height
            for k in range(i+1, n):
                if height[k] > height[i]:
                    max_right = max(max_right, height[k])
            
            # calculate the area 
            if min(max_left, max_right) > height[i]:
                ans += min(max_left, max_right) - height[i]
        return ans

c++实现

class Solution {
    
public:
    int trap(vector<int>& height) {
    
        int n = height.size();
        if (n < 3)
            return 0;
        
        int ans = 0;
        for (int i=1; i<n-1; i++) {
    
            int max_left = 0, max_right = 0;
            for (int j=0; j<i; j++) {
    
                max_left = max(max_left, height[j]);
            }
            for (int k=i+1; k<n; k++) {
    
                max_right = max(max_right, height[k]);
            }

            if (min(max_left, max_right) > height[i])
                ans += min(max_left, max_right) - height[i];
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度： $O(n^2)$
• 空间复杂度： $O(1)$

动态规划

python实现

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n < 3:
            return 0
        
        # dp 空间换时间，记录左右大小
        max_lefts = []  # 从左往右
        max_rights = []  # 从右往左
        max_left = 0
        max_right = 0
        for i in range(n):
            if height[i] > max_left:
                max_left = height[i]
            max_lefts.append(max_left)
        
        for j in range(n-1, -1, -1):
            if height[j] > max_right:
                max_right = height[j]
            max_rights.insert(0, max_right)
        
        ans = 0
        # loop for calc every column
        for i in range(1, n-1):
            max_left = max_lefts[i]
            max_right = max_rights[i]
            ans += min(max_left, max_right) - height[i]
        return ans
            

c++实现

class Solution {
    
public:
    int trap(vector<int>& height) {
    
        int n = height.size();
        if (n < 3)
            return 0;
        
        vector<int> left_maxs(n);
        vector<int> right_maxs(n);

        left_maxs[0] = height[0];
        right_maxs[n-1] = height[n-1];

        for (int i=1; i<n; i++) {
    
            left_maxs[i] = max(left_maxs[i-1], height[i]);
        }

        for (int j=n-2; j>=0; j--) {
    
            right_maxs[j] = max(right_maxs[j+1], height[j]);
        }

        int ans = 0;
        for (int i=0; i<n; i++) {
    
            ans += min(left_maxs[i], right_maxs[i]) - height[i];
        }
        return ans;
    }
};

单调栈

python实现

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n < 3:
            return 0

        # 单调栈
        stack = []  # 栈底到栈顶的下标对应的元素高度递减，当遇着比之大的元素，出栈，并计算面积，此时左右最大边界也知道 
        ans = 0
        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                top = stack.pop()  # 此时柱子的高度， h为右边界
                if not stack:
                    break
                
                left = stack[-1]
                current_width = i - left - 1
                current_hight = min(height[left], h) - height[top]
                ans += current_hight * current_width
            stack.append(i)
        return ans

c++实现

class Solution {
    
public:
    int trap(vector<int>& height) {
    
        int n = height.size();
        if (n < 3)
            return 0;
        
        vector<int> stack;
        int ans = 0;
        for (int i=0; i<n; i++) {
    
            while (stack.size() !=0 && height[i] > height[stack.back()]) {
    
                int tmp = stack.back();
                stack.pop_back();
                if (stack.size() == 0)
                    break;
                int left_height = height[stack.back()];
                int current_width = i - stack.back() - 1;
                int current_height = min(left_height, height[i]) - height[tmp];
                ans += current_height * current_width;
            }
            stack.push_back(i);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度： $O(n)$
• 空间复杂度：$O(n)$

双指针

python实现

class Solution:
    def trap(self, height: List[int]) -> int:
        # 双指针
        n = len(height)
        if n < 3:
            return 0
        
        left = 0
        right = n-1
        ans = 0
        left_max = height[left]
        right_max = height[right]
        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])
            if left_max < right_max:
                ans += left_max - height[left]
                left += 1
            else:
                ans += right_max - height[right]
                right -= 1
        return ans

c++实现

class Solution {
    
public:
    int trap(vector<int>& height) {
    
        int n = height.size();
        if (n < 3)
            return 0;
        
        int ans = 0;
        int left = 0, right = n-1;
        int left_max = height[left], right_max = height[right];
        while (left < right) {
    
            left_max = max(left_max, height[left]);
            right_max = max(right_max, height[right]);
            if (left_max < right_max) {
    
                ans += left_max - height[left];
                left++;
            }
            else {
    
                ans += right_max - height[right];
                right--;
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度： $O(n)$
• 空间复杂度：$O(1)$

参考

• https://leetcode.cn/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/