接雨水问题

问题1

盛水最多的容器

原理

• 首先想到最多的容器肯定是：Min(两个柱子)*(柱子之间间距)
• 遍历一次需要找到最多的容器，应该采用双指针算法，并且使用max作为临时变量记录下来

代码

class Solution {
    public int maxArea(int[] arr) {
      if(arr==null||arr.length<=0){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int low = 0;
        int high = arr.length-1;

        while(low<high){
            int cur = Math.min(arr[low],arr[high]);
            max = Math.max(max,cur*(high-low));
            if(arr[low]<arr[high]){
                low++;
            }else{
                high--;
            }
        }
        return max;
    }
}

注意事项

• 注意联想到双指针就能cover住

问题2

接雨水的总和最大

原理

• 处理这个问题还是需要使用双指针
• 雨水的最大值应该是min(Math.max(height[left],leftMax),Math.max(height[right],rightMax)) 简单解释就是左边最大值和右边最大值，之后的最小值决定了两边围栏的高度。当前实际的蓄水量减去当前值就OK了。

代码

class Solution {
    public int trap(int[] arr) {
        if(arr==null||arr.length<=0){
            return 0;
        }
        int max = 0;
        int low = 0;
        int high = arr.length-1;

        int leftmax = arr[0];
        int rightmax = arr[arr.length-1];

        while(low<high){
            leftmax = Math.max(leftmax,arr[low]);
            rightmax = Math.max(rightmax,arr[high]);

            if(arr[low]<arr[high]){
                max += Math.min(leftmax,rightmax)-arr[low];
                low++;
            }else{
                max += Math.min(leftmax,rightmax)-arr[high];
                high--;
            }
        }
        return max;
    }
}

注意事项

• 注意雨水存储实际上一个一个比较计算出来的。
• 解决问题的关键在于min(Math.max(height[left],leftMax),Math.max(height[right],rightMax))- min(height[low],height[high]);

问题3

柱状图中最大的矩形

原理

代码

注意事项