接雨水「变题」

42. 接雨水

// 单调栈
// 时间复杂度 : O(n)
// 空间复杂度 : O(n)
public int trap(int[] height) {
    int ans = 0;
    Deque<Integer> s = new ArrayDeque<>();
    for (int i = 0; i < height.length; i++) {
        while (!s.isEmpty() && height[s.peek()] < height[i]) {
            int top = s.poll();
            if (s.isEmpty()) break;
            int left = s.peek();
            int curWidth = i - left - 1;
            int curHeight = Math.min(height[i], height[left]) - height[top];
            ans += curHeight * curWidth;
        }
        s.push(i);
    }
    return ans;
}

// 双指针
// 时间复杂度 : O(n)
// 空间复杂度 : O(1)
public int trap(int[] height) {
    int curH = 0, ans = 0;
    int l = 0, r = height.length - 1;
    while (l < r) {
        if (height[l] <= height[r]) {
            ans += Math.max(0, curH - height[l]);
            curH = Math.max(curH, height[l]);
            l++;
        } else {
            ans += Math.max(0, curH - height[r]);
            curH = Math.max(curH, height[r]);
            r--;
        }
    }
    return ans;
}

变题一：二维接雨水

题目详情可见 接雨水 II

木桶原则，从最外圈开始向内收缩

public int trapRainWater(int[][] heightMap) {
    int m = heightMap.length, n = heightMap[0].length;
    boolean[][] vis = new boolean[m][n];
    Queue<int[]> q = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    for (int i = 0; i < m; i++) {
        q.offer(new int[]{i, 0, heightMap[i][0]});
        q.offer(new int[]{i, n - 1, heightMap[i][n - 1]});
        vis[i][0] = true;
        vis[i][n - 1] = true;
    }
    for (int i = 0; i < n; i++) {
        q.offer(new int[]{0, i, heightMap[0][i]});
        q.offer(new int[]{m - 1, i, heightMap[m - 1][i]});
        vis[0][i] = true;
        vis[m - 1][i] = true;
    }
    int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    int ans = 0;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        for (int[] dir : dirs) {
            int nx = cur[0] + dir[0], ny = cur[1] + dir[1];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || vis[nx][ny]) continue;
            ans += Math.max(0, cur[2] - heightMap[nx][ny]);
            q.offer(new int[]{nx, ny, Math.max(cur[2], heightMap[nx][ny])});
            vis[nx][ny] = true;
        }
    }
    return ans;
}