LeetCode42.接雨水、LeetCode11. 盛最多水的容器

冷不防 2021-09-21 05:46 202阅读 0赞

> 单调栈、动态规划、双指针

### LeetCode42.接雨水 ###

**【题目】**

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

**【输入】**: \[0,1,0,2,1,0,1,3,2,1,2,1\]

**【输出】**: 6

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

**【解法一】：暴力解法**

思路：对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。每次计算的当前元素能存储的雨水，最后累计即可

*  首尾元素无须计算
 *  当左右无大于当前元素的值值，当前位置无法存储雨水

public int method1(int[] arr) { 
            if(arr.length==0 || arr==null) return 0;
    
            int i,j,res,left,right,leftMax,rightMax;
    
            res = 0;
            for (i=1; i<arr.length-1; i++) { 
                left = i;
                right = i;
                leftMax = rightMax = 0;
                // 向左寻找大于当前元素的最大值
                while (left>=0) { 
                    if (arr[left] > arr[i] && leftMax < arr[left]) leftMax = arr[left];
                    left--;
                }
                // 向右寻找大于当前元素的最大值
                while (right<arr.length) { 
                    if (arr[right] > arr[i] && rightMax < arr[right]) rightMax = arr[right];
                    right++;
                }
                if (leftMax != 0 && rightMax != 0) { 
                    res += Math.min(leftMax,rightMax) - arr[i];
                }
            }
    
            return res;
        }

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

**【解法二】动态规划**

在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以用动态规划的方式提前存储这个值。

/** * 在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。 * 但是我们可以提前存储这个值。因此，可以通过动态编程解决。 * * dp1[x] 从0达到x的时候，已有的最大值 * dp2[x] 从n-1到达x的时候，已有的最大值 * */
        public int method2(int[] a) { 
    
            if(a.length==0 || a==null) return 0;
    
            int i,res;
            int[] dp1,dp2;
            dp1 = new int[a.length];
            dp2 = new int[a.length];
    
            dp1[0] = a[0];
            dp2[a.length-1] = a[a.length-1];
    
            for (i=1; i<a.length; i++) { 
                dp1[i] = Math.max(dp1[i-1],a[i]);
            }
    
            for (i=a.length-2; i>=0; i--) { 
                dp2[i] = Math.max(dp2[i+1],a[i]);
            }
    
            res = 0;
            for (i=1; i<a.length-1; i++) { 
                if (a[i]<dp1[i] && a[i]<dp2[i]) { 
                    res += Math.min(dp1[i],dp2[i]) - a[i];
                }
            }
    
            return res;
        }

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

**【解法三】单调栈**

/** * 利用单调栈 * 栈顶元素大于当前元素，当前元素入栈 * 等于和小于要进行相应的计算 * * 单调栈存下标要比存内容的意义更大，因为可以通过下标定位到元素 * */
        public int method3(int[] a) { 
            if (a==null || a.length==0) return 0;
    
            Stack<Integer> stack = new Stack<>();
    
            int i,res;
    
            res = 0;
            for (i=0; i<a.length; i++) { 
                while (!stack.empty() && a[stack.peek()] < a[i]) { 
                    int curIndex = stack.pop();
    				// 需要把相同的元素全部弹出栈
                    while (!stack.empty() && a[curIndex] == a[stack.peek()]) { 
                        curIndex = stack.pop();
                    }
    
                    if (!stack.empty()) { 
                        int leftIndex = stack.peek();
                        int height = Math.min(a[i],a[leftIndex])-a[curIndex];
                        int width = i - leftIndex - 1;
                        res += height * width;
                    }
                }
                stack.add(i);
            }
    
            return res;
        }

注意：单调栈存下标要比存内容的意义更大，因为可以通过下标定位到元素

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

### LeetCode11. 盛最多水的容器 ###

**【题目】**

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]  
**【示例】**

输入：\[1,8,6,2,5,4,8,3,7\]  
输出：49

**【思考】**

**方法一：动态规划**

dp1\[x\] 从0到x-1，第一个大于等于a\[x\]的下标，没有则为-1  
dp2\[x\] 从n-1到x+1，第一个大于等于a\[x\]的下标，没有则为-1  
从两个方向来讨论，可以避免单方向的很多情况的讨论

然后遍历，以当前高度为高，以左右两边最大值到当前的距离为宽，计算最大值  
**时间复杂度：O（n2）**

**方法二：双指针**  
左右两个指针放在队首和队尾，计算出当前双指针的面积  
然后移动较低指针，重新计算面经，并记录最大面积值（为什么移动较低，思考一下移动较低和较高到下一个柱子，与原有面积的关系就可以得出了）

**【代码】**

package LeetCode;
    
    import java.util.Arrays;
    
    public class LeetCode11 { 
        /** * dp1[x] 从0到x-1，第一个大于等于a[x]的下标，没有则为-1 * dp2[x] 从n-1到x+1，第一个大于等于a[x]的下标，没有则为-1 * 从两个方向来讨论，可以避免单方向的很多情况的讨论 * * dp[x] = dp[x-1] {a[x]<=a[x-1]} * */
        public int maxArea1(int[] height) { 
            if (height==null || height.length==0)
                return 0;
    
            int n,max,i,j;
            n = height.length;
            int[] dp1 = new int[n];
            int[] dp2 = new int[n];
            Arrays.fill(dp1,-1);
            Arrays.fill(dp2,-1);
    
            dp1[0] = 0;
            for (i=1; i<n; i++) { 
                if (height[i]<=height[i-1] && dp2[i-1]!=-1) { 
                    dp1[i] = dp1[i-1];
                } else { 
                    for (j=0; j<i; j++) { 
                        if (height[i]<=height[j]) { 
                            dp1[i] = j;
                            break;
                        }
                    }
                }
            }
    
            dp2[n-1] = n-1;
            for (i=n-2; i>=0; i--) { 
                if (height[i]<=height[i+1] && dp2[i+1]!=-1) { 
                    dp2[i] = dp2[i+1];
                } else { 
                    for (j=n-1; j>i; j--) { 
                        if (height[i]<=height[j]) { 
                            dp2[i] = j;
                            break;
                        }
                    }
                }
            }
    
            int[] res = new int[n];
            max = 0;
            for (i=0; i<n; i++) { 
                if (dp1[i]!=-1 && dp2[i]!=-1) { 
                    res[i] = Math.max((i-dp1[i])*height[i],(dp2[i]-i)*height[i]);
                } else if (dp1[i]!=-1 && dp2[i]==-1) { 
                    res[i] = (i-dp1[i])*height[i];
                } else if (dp1[i]==-1 && dp2[i]!=-1) { 
                    res[i] = (dp2[i]-i)*height[i];
                }
                if (max < res[i]) max = res[i];
            }
    
            return max;
        }
    
        /** * 双指针法 * 左右两个指针放在队首和队尾，计算出当前双指针的面积 * 然后移动较低指针，重新计算面经，并记录最大面积值 * */
        public int maxArea(int[] height) { 
            if (height==null || height.length==0)
                return 0;
    
            int l,r,len,max,min;
            len = height.length;
            l = 0;
            r = len-1;
            max = 0;
            while (l<r) { 
                min = Math.min(height[l],height[r]);
                max = Math.max(min*(r-l),max);
                if (height[l]==min) { 
                    l++;
                } else { 
                    r--;
                }
            }
    
            return max;
        }
    
        public static void main(String[] args) { 
            int[] a = { 1,8,1};
            System.out.println(new LeetCode11().maxArea(a));
        }
    }

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

**【Java 面试那点事】**

**这里致力于分享 Java 面试路上的各种知识，无论是技术还是经验，你需要的这里都有！**

**这里可以让你【快速了解 Java 相关知识】，并且【短时间在面试方面有跨越式提升】**

**面试路上，你不孤单！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/548a54f6d74740cbafa9f15cf151448e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]: /images/20210920/75a865f814034783a8abf4e3cc54a44a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 2]: /images/20210920/9385333775be455980c9004d7599afe7.png