题目链接

接雨水

题目描述

image.png

实现代码

简单思想：对于每一个位置i，其能积水的情况为：height[i] 比当前位置左右两边的列表最大值left_max和right_max都要小；积水量为：min(left_max, right_max) - height[i]

实现代码如下：

  1. class Solution {
  2.     public int trap(int[] height) {
  4.         int len = height.length;
  5.         if (len == 1) {
  6.             return 0;
  7.         }
  9.         int result = 0;
  11.         int left_max = height[0];
  12.         for (int i = 1; i < len - 1; i++) {
  14.             if(left_max <= height[i]) {
  15.                 left_max = height[i];
  16.                 continue;
  17.             }
  19.             // find right max
  20.             int right_max = height[i + 1];
  21.             for (int j = i + 2; j < len; j++) {
  22.                 if (right_max < height[j]) {
  23.                     right_max = height[j];
  24.                 }
  25.             }
  27.             // update result
  28.             if (left_max <= height[i] || right_max <= height[i]) {
  29.                 left_max = left_max < height[i] ? height[i] : left_max;
  30.                 continue;
  31.             }
  32.             result += Math.min(left_max, right_max) - height[i];
  33.         }
  35.         return result;
  37.     }
  38. }

在前面方法实现的基础上进行优化，我们可以先分别进行两次遍历计算每个位置的左边最大值和右边最大值，这样就能将复杂度降为O(n)了，如图示：
image.png