灌水问题

Trapping Rain Water

核心就是得到每个位置左右的两边的最大高度。

左右两边的柱子决定了灌水的基调。

// 这道题每个bar能承受的最大水量和其两边的最大高度有关。 所以我们可以用两个数组分别存储其两边的最大高度。
// 取两边最大高度短的那个和当前的高度进行比较，差值就是盛水量。
// space: O(n)
public int trap(int[] height) {
    int n = height.length;
    int[] left = new int[n];
    int[] right = new int[n];

    int max = 0;
    for(int i = 0; i < n; i++) {
        max = Math.max(max, height[i]);
        left[i] = max;
    }

    max = 0;

    for(int i = n - 1; i >= 0; i--) {
        max = Math.max(max, height[i]);
        right[i] = max;
    }

    int sum = 0;

    for(int i = 0; i < n; i++) {
        sum += Math.min(left[i], right[i]) - height[i];
    }

    return sum;
}

// 借用Maximum Rectangle in Histogram 的单调栈的思想
// 我们可以one pass的解决这个问题
// 用一个stack来储存其两边大的数，所以是递减栈
// space O(n)
public int trap(int[] height) {
    // arrayDeque is fast than stack and queue and prefer to use
    // stack store index
    Deque<Integer> stack = new ArrayDeque<>();
    int sum = 0;
    int n = height.length;
    for(int i = 0; i < n; i++) {
        int cur = height[i];

        while(!stack.isEmpty() && height[stack.peek()] < cur) {
            int base = stack.pop();
            if(!stack.isEmpty()) {
                int h = Math.min(height[stack.peek()], cur) - height[base];
                int width = i - stack.peek() - 1;
                sum += h * w;
            }
        }

        stack.push(i);
    }
    return sum;
}


// 其实空间上还是可以继续优化的
// 还有一种两个指针一次扫描的情况，这种两边往中间夹逼的方法也挺常用的，它的核心思路就是向中间夹逼时能确定接下来移动一侧窗口不可能使结果变得更好，所以每次能确定移动一侧指针，直到相遇为止。
// 木桶原理的算法版，最两边的板子形成一个木桶，由两块板子最低的那块决定水位。每次都从两边最低的方向向里扫描。

// 因为 i,j 当前高度未必是当前左右两边最高高度，每次更新的时候要注意维护下。
// O(1)
public int trap(int[] height) {
    int n = height.length;
    int i = 0;
    int j = n - 1;
    int leftMax = height[i];
    int rightMax = height[j];
    int sum = 0;

    while(i < j) {
        if(leftMax < rightMax) {
            // 中间需要有间隔 所以i + 1 < n
            if(i + 1 < n && height[i + 1] < leftMax) {
                sum += leftMax - height[i + 1];
            }
            i++;
            // update leftmax
            leftMax = Math.max(leftMax, heigth[i]);
        } else {
            if(j - 1 >= 0 && height[j - 1] < rightMax) {
                sum += rightMax - height[j - 1];
            }
            j--;
            rightMax = Math.max(rightMax, height[j]);
        }
    }

    return sum;
}

Trapping Rain Water II

这道题沿用上一题的思想，从四周往中间去逼近，四周柱子的最小值决定了灌水的基调。

然后从四周的最小值往中间走，看哪些点没有访问过，如果柱子的高度小于当前高度，那么此处就可以灌水，并且更新四周围栏。

因为需要获得四周柱子的最小值，我们就需要heap，可以快速获得最小值。 因为需要看哪些点没有访问过，所以我们需要一个array来记录是否访问过。

public class Solution {
    class Cell implements Comparable<Cell> {
        int x, y, height;
        public Cell(int x, int y, int height) {
            this.x = x;
            this.y = y;
            this.height = height;
        }

        // min heap
        public int compareTo(Cell other) {
            return this.height - other.height;
        }
    }

    int[] dx = {1,0,-1,0};
    int[] dy = {0,1,0,-1};
    public int trapRainWater(int[][] heightMap) {
        if(heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) return 0;

        int m = heightMap.length;
        int n = heightMap[0].length;

        boolean[][] visited = new boolean[m][n];

        PriorityQueue<Cell> pq = new PriorityQueue<Cell>();

        // add all around cells to heap
        for(int i = 0; i < m; i++) {
            pq.offer(new Cell(i, 0, heightMap[i][0]));
            visited[i][0] = true;

            pq.offer(new Cell(i, n - 1, heightMap[i][n - 1]));
            visited[i][n - 1] = true;
        }

        for(int i = 0; i < n; i++) {
            pq.offer(new Cell(0, i, heightMap[0][i]));
            visited[0][i] = true;

            pq.offer(new Cell(m - 1, i, heightMap[m - 1][i]));
            visited[m - 1][i] = true;
        }

        int count = 0;

        while(!pq.isEmpty()) {
            Cell cur = pq.poll();

            for(int i = 0; i < 4; i++) {
                int x = cur.x + dx[i];
                int y = cur.y + dy[i];

                if(x > 0 && y > 0 && x < m && y < n && !visited[x][y]) {
                    visited[x][y] = true;

                    pq.offer(new Cell(x, y, Math.max(cur.height, heightMap[x][y])));
                    count += Math.max(0, cur.height - heightMap[x][y]);
                }
            }
        }
        return count;       
    }
}