首页 > 代码库 > [LeetCode] 407. Trapping Rain Water II
[LeetCode] 407. Trapping Rain Water II
https://leetcode.com/problems/trapping-rain-water-ii/
public class Solution { class Cell { public int x; public int y; public int value; public Cell(int x, int y, int value) { this.x = x; this.y = y; this.value =http://www.mamicode.com/ value; } } public int trapRainWater(int[][] heightMap) { int level = 0; int result = 0; if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) { return result; } boolean[][] visited = new boolean[heightMap.length][heightMap[0].length]; int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; PriorityQueue<Cell> queue = new PriorityQueue<Cell>(new Comparator<Cell>() { public int compare(Cell c1, Cell c2) { return c1.value - c2.value; } }); for (int i = 0; i < heightMap.length; i++) { for (int j = 0; j < heightMap[0].length; j++) { if (i == 0 || j == 0 || i == heightMap.length - 1 || j == heightMap[0].length - 1) { queue.offer(new Cell(i, j, heightMap[i][j])); visited[i][j] = true; } else { visited[i][j] = false; } } } while (!queue.isEmpty()) { Cell current = queue.poll(); int height = current.value; level = Math.max(height, level); for (int[] move : dir) { int x = current.x + move[0]; int y = current.y + move[1]; if (x >= 0 && x < heightMap.length && y >= 0 && y < heightMap[0].length && visited[x][y] == false) { result += heightMap[x][y] < level ? level - heightMap[x][y] : 0; visited[x][y] = true; queue.offer(new Cell(x, y, heightMap[x][y])); } } } return result; } }
参考:http://www.cnblogs.com/grandyang/p/5928987.html
[LeetCode] 407. Trapping Rain Water II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。