面试题 17.21 直方图的水量

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 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

题解1：暴力法
这次代码算是简洁了，但是复杂度上天。具体来讲就是自底向上每行横着刷一遍，看到可以积水的地方就把空间加上。第一种是一行一行刷，第二种优化了一下，按高度的跨度几行几行刷。

class Solution {
    int[] height;
    public int trap(int[] ht) {
        height = ht.clone();
        int n = height.length, counting, capacity=0, tmp;
        if(n<3)
            return 0;
        Arrays.sort(ht);
        for(int i=1;i<=ht[n-2];++i){
            counting=0;
            tmp=0;
            for(int j=0;j<n;++j){
                if(height[j]>=i){
                    counting=1;
                    if(tmp>0){
                        capacity+=tmp;
                        tmp=0;
                    }
                }
                else if(counting==1){
                    tmp++;
                }
            }
        }
        return capacity;
    }
}

class Solution {
    int[] height;
    public int trap(int[] ht) {
        height = ht.clone();
        int n = height.length, counting, capacity=0, tmp;
        Arrays.sort(ht);
        LinkedHashSet<Integer> set=new LinkedHashSet<Integer>();
        for (int item:
             ht) {
            set.add(item);
        }
        int former = 0;
        for (int box:
             set) {
            if(box==ht[0]){
                former=box;
            }
            else if(box<=ht[n-2]){
                counting=0;
                tmp=0;
                int increase = box-former;
                for (int i : height) {
                    if (i >= box) {
                        counting = 1;
                        if (tmp > 0) {
                            capacity += tmp;
                            tmp = 0;
                        }
                    } else if (counting == 1) {
                        tmp += increase;
                    }
                }
                former = box;
            }
        }
        return capacity;
    }
}

题解2：动态规划
我觉得不能算是严格意义上的动态规划，只是一种空间换取时间的简单策略，且没有任何代价函数及子问题可言。思路很简单，分别自左自右扫描一遍，看看每一列元素左方与右方的最大值，从而确定该列究竟能装多高的水量。

class Solution {
    int[] height;
    public int trap(int[] height) {
        int n = height.length;
        int[] leftHeight = new int[n];
        int[] rightHeight = new int[n];
        int capacity=0;
        int maxHeight = 0;
        for(int i=0;i<n;++i){
            if(height[i]>maxHeight)
                maxHeight = height[i];
            leftHeight[i] = maxHeight;
        }
        maxHeight = 0;
        for(int i=n-1;i>=0;--i){
            if(height[i]>maxHeight)
                maxHeight = height[i];
            rightHeight[i] = maxHeight;
        }
        for(int i=0;i<n;++i){
            capacity+=(Math.min(leftHeight[i], rightHeight[i])-height[i]);
        }
        return capacity;
    }
}

题解3：单调栈

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;
    }
}

题解4：双指针

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}