题解 | #接雨水问题#

接雨水问题

1、题意重述

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

换句话说，即根据数组每个位置数值的大小，对左右两边的高度值进行判断，进而得到接水量。

2、思路整理

使用双指针的思想：

Step1:首先找到最高的柱子，然后以这个柱子划分为左半部分和右半部分。

Step2：对于左半部分，使用两个指针left和right分别指向左半部分的两个柱子。

如果left指向的柱子高于right指向的柱子，那么此时可以接水，并且接水量为left-right。

如果left指向的柱子不高于right指向的柱子，那么此时是不可以接水的，我们便更新left，让其指向right指向的柱子。

Step3：重复Step2，让left更新到最高柱子的位置，结束左半部分。

Step4：对于右半部分，重复Step2和Step3的操作，此时更新right指针，当right指针指向最高柱子时，结束右半部分。

Step5：将左右两个部分的接水量相加，返回结果。

3、代码实现

  public long maxWater(int[] arr) {
      if (arr.length <= 2)
          return 0;
      //找到最高柱子
      int max = Integer.MIN_VALUE;
      int maxIndex = -1;
      for (int i = 0; i < arr.length; i++) {
          if (arr[i] > max) {
              max = arr[i];
              maxIndex = i;
          }
      }

      //统计左边接水量
      int left = arr[0];
      int right = 0;
      long water = 0;
      for (int i = 1; i < maxIndex; i++) {
          right = arr[i];
          if (right > left) {
              left = right;
          } else {
              water += left - right;
          }
      }

      //统计右边接水量
      right = arr[arr.length - 1];
      for (int i = arr.length - 2; i > maxIndex; i--) {
          left = arr[i];
          if (arr[i] > right) {
              right = left;
          } else {
              water += right - left;
          }
      }
      return water;
  }

4、复杂度分析

时间复杂度：一遍循环，因此时间复杂度为$O(N)O(N)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。