LeetCode 42. 接雨水

深藏阁楼爱情的钟 2022-10-31 04:27 170阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210221200658936.png]  
[官方题解 我拜倒][Link 1]

//解法一：暴力枚举寻找某个位置的左边最大和右边最大
    public int trap(int[] height) {
        
        int ans = 0;
        int size = height.length;
        for (int i = 1; i < size - 1; i++) {
        
            int max_left = 0, max_right = 0;
            for (int j = i; j >= 0; j--) {
         //Search the left part for max bar size
                max_left = Math.max(max_left, height[j]);
            }
            for (int j = i; j < size; j++) {
         //Search the right part for max bar size
                max_right = Math.max(max_right, height[j]);
            }
            ans += Math.min(max_left, max_right) - height[i];
        }
        return ans;
    }

//解法二：用额外空间记录某个位置的左边最大和右边最大  58%
    public int trap(int[] height) {
        
        if (height == null || height.length == 0)
            return 0;
        int ans = 0;
        int size = height.length;
        int[] left_max = new int[size];
        int[] right_max = new int[size];
        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
        
            left_max[i] = Math.max(height[i], left_max[i - 1]);
        }
        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
        
            right_max[i] = Math.max(height[i], right_max[i + 1]);
        }
        for (int i = 1; i < size - 1; i++) {
        
            ans += Math.min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }

//解法三：单调递减栈 28%
    class Solution {
        
        public int trap(int[] height) {
        
            Stack<Integer> st = new Stack<Integer>();
            int i = 0;
            int ans = 0;
            while(i < height.length){
        
                while(!st.empty() && height[i] > height[st.peek()]){
        
                    int top = st.pop();
                    if(st.empty())
                        break;
                    int distance = i - st.peek() - 1;
                    int bounded_height = Math.min(height[i], height[st.peek()]) - height[top];
                    ans += distance * bounded_height;
                }
                st.push(i++);
            }
            return ans;
        }
    }

//解法四 ： 双指针才是最快的 从两端逼近 计算 两边的最大值 很厉害
    class Solution {
        
        public int trap(int[] height) {
        
            int n = height.length;
            int l = 0;
            int r = n - 1;
            int lmax = 0;
            int rmax = 0;
            int ans = 0;
            while(l < r){
        
                if(height[l] < height[r]){
        
                    if(height[l] > lmax)
                        lmax = height[l];
                    else
                        ans += lmax - height[l];
                    l++;
                }else{
        
                    if(height[r] > rmax)
                        rmax = height[r];
                    else
                        ans += rmax - height[r];
                    r--;
                }
            }
            return ans;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/b99f8bd56dd44483821cf3a59e2fcaa6.png
[20210221200658936.png]: /images/20221024/dceb8167b8b04e02bec481376081f884.png
[Link 1]: https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/