直方图的水量

面试题 17.21. 直方图的水量

难度困难106

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

示例:

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

双指针

只要左边目前的最大值小于右边目前的最大值，那么当前位置盛水的能力就由左边的最大值决定，直接处理左边的部分，否则目前盛水的最大值由右边决定，需要从右边开始处理。

如果右边目前的最大值小于左边目前的最大值，那么当前位置盛水的能力就由右边的最大值决定，直接处理右边的部分，否则目前盛水的最大值由左边决定，需要从左边开始处理。

class Solution {
    public int trap(int[] height) {
        int n=height.length;

        int leftMax=0,rightMax=0;
        int l=0,r=n-1;

        int res=0;

        while(l<=r){
            if(leftMax<=rightMax){
                res += Math.max(leftMax-height[l],0);
                leftMax = Math.max(leftMax,height[l]);
                l++;
            }else{
                res += Math.max(rightMax - height[r],0);
                rightMax = Math.max(rightMax,height[r]);
                r--;
            }
        }
        return res;
    }
}

动态规划

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        // 正向遍历获取从左到右当前位置之前的最大值
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        // 反向遍历获取从右往左当前位置之后的最大值
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        // 盛水的最大值由左右两边的最大值中较小的那个减去当前位置的值决定
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci/solution/zhi-fang-tu-de-shui-liang-by-leetcode-so-7rla/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

单调栈

单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 $\textit{height}$ 中的元素递减。

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        // 这是一个单调栈
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                // 如果栈中只有一个元素,那么跳出
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci/solution/zhi-fang-tu-de-shui-liang-by-leetcode-so-7rla/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信