动态规划

image.png

木桶效应 - 底座高度

动态规划？还是不懂这怎么就是动态规划了~

两个数组：

  • leftMax ：每个位置的左侧 max
  • rightMax：每个位置的右侧 max
  1.     /**
  2.      * 动态规划的实现 （这就叫动态规划吗？）
  3.      * @param height 数组
  4.      * @return 雨量
  5.      */
  6.     public int trap(int[] height) {
  8.         final int length = height.length;
  9.         // 左侧最大值
  10.         int[] lm = new int[length];
  11.         // 右侧最大值
  12.         int[] rm = new int[length];
  14.         lm[0] = height[0];
  15.         rm[length - 1] = height[length - 1];
  16.         for (int i = 1; i < length; i++) {
  17.             lm[i] = Math.max(height[i], lm[i - 1]);
  18.         }
  19.         for (int i = length - 2; i >= 0; i--) {
  20.             rm[i] = Math.max(height[i], rm[i + 1]);
  21.         }
  23.         System.out.println(Arrays.toString(lm));
  24.         System.out.println(Arrays.toString(rm));
  26.         int ans = 0;
  27.         for (int i = 0; i < height.length; i++) {
  28.             ans = ans + Math.min(lm[i], rm[i]) - height[i];
  29.         }
  30.         return ans;
  31.     }

单调栈

image.png

单调栈、单调递减
我理解的是“计算凹槽的体积”，找到所有的凹槽~
凹槽的特点：先递减，再递增

还是不是很理解~

三维

image.png

water[i][j] =
max(
heightMap[i][j],
min(water[i−1][j],water[i+1][j],water[i][j−1],water[i][j+1])
)

图上的公式错了呀~
image.png

  1.         if (heightMap.length <= 2 || heightMap[0].length <= 2) {
  2.             return 0;
  3.         }
  4.         int m = heightMap.length;
  5.         int n = heightMap[0].length;
  6.         boolean[][] visit = new boolean[m][n];
  7.         PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
  9.         for (int i = 0; i < m; ++i) {
  10.             for (int j = 0; j < n; ++j) {
  11.                 if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
  12.                     pq.offer(new int[]{i * n + j, heightMap[i][j]});
  13.                     visit[i][j] = true;
  14.                 }
  15.             }
  16.         }
  17.         int res = 0;
  18.         int[] dirs = {-1, 0, 1, 0, -1};
  19.         while (!pq.isEmpty()) {
  20.             int[] curr = pq.poll();
  21.             for (int k = 0; k < 4; ++k) {
  22.                 int nx = curr[0] / n + dirs[k];
  23.                 int ny = curr[0] % n + dirs[k + 1];
  24.                 if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
  25.                     if (curr[1] > heightMap[nx][ny]) {
  26.                         res += curr[1] - heightMap[nx][ny];
  27.                     }
  28.                     pq.offer(new int[]{nx * n + ny, Math.max(heightMap[nx][ny], curr[1])});
  29.                     visit[nx][ny] = true;
  30.                 }
  31.             }
  32.         }
  33.         return res;