当前位置：网站首页>[数组]BM94 接雨水问题-较难

[数组]BM94 接雨水问题-较难

2022-06-27 03:33:00 【51CTO】

描述

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

数据范围：数组长度 [数组]BM94 接雨水问题-较难_数组_02 ，数组中每个值满足 [数组]BM94 接雨水问题-较难_双指针_03 ，保证返回结果满足 [数组]BM94 接雨水问题-较难_双指针_04 要求：时间复杂度 [数组]BM94 接雨水问题-较难_数组_05

示例1

输入：

      
      
       
       [3,1,2,5,2,4]
      
      
      
      
       
       1.

复制返回值：

复制说明：

      
      
       
       数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。
      
      
      
      
       
       1.

示例2

输入：

      
      
       
       [4,5,1,3,2]
      
      
      
      
       
       1.

复制返回值：

题解

辅助数组解法

思路：

假设数组为a，对于任意下标i，它能盛水的容量取决于它左右两边最高的2根中低的那一根，假设该高度为h，盛水的容量则为h - a[i]。我们只要找出对于任意下表i，它左右最高

步骤如下：

试用2个数组max_left[i]和max_right[i]分别代表到下标i的时候，左边[0,i-1]最高的柱子，以及从右往左[n-1,i+1]最高的柱子，遍历数组，先求解这两个数组
再次遍历数组，当到达下标i的时候，该柱子盛水的容量为v = min(max_left[i],max_right[i]) - arr[i]
将第二步进行累计即可得到答案

代码如下：

       
       // https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       long 
       
       long 
       
       maxWater(
       
       vector
       
       <
       
       int
       
       > 
       
       &
       
       arr)
       
{
       
       if (
       
       arr.
       
       size() 
       
       <= 
       
       2)
       
  {
       
       return 
       
       0;
       
  }
       
       std::vector
       
       <
       
       int
       
       > 
       
       max_left(
       
       arr.
       
       size(), 
       
       0);
       
       std::vector
       
       <
       
       int
       
       > 
       
       max_right(
       
       arr.
       
       size(), 
       
       0);
       
       for (
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       < 
       
       arr.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       max_left[
       
       i] 
       
       = 
       
       std::max(
       
       max_left[
       
       i 
       
       - 
       
       1], 
       
       arr[
       
       i 
       
       - 
       
       1]);
       
  }
       
       for (
       
       int 
       
       i 
       
       = 
       
       arr.
       
       size() 
       
       - 
       
       2; 
       
       i 
       
       >= 
       
       0; 
       
       --
       
       i)
       
  {
       
       max_right[
       
       i] 
       
       = 
       
       std::max(
       
       max_right[
       
       i 
       
       + 
       
       1], 
       
       arr[
       
       i 
       
       + 
       
       1]);
       
  }
       
       int 
       
       res 
       
       = 
       
       0;
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       arr.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       int 
       
       h 
       
       = 
       
       std::min(
       
       max_left[
       
       i], 
       
       max_right[
       
       i]);
       
       if (
       
       h 
       
       > 
       
       arr[
       
       i])
       
    {
       
       res 
       
       += (
       
       h 
       
       - 
       
       arr[
       
       i]);
       
    }
       
  }
       
       return 
       
       res;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.

双指针解法

在上面的解法中我们使用了2个辅助数组来存放某一下标i的左右最大高度。那么我们可不可以在不使用辅助数组的情况下知道下标i的左右最大高度呢？其实思考一下就很容易知道了，使用双指针可以很容易的写出答案。

步骤：

使用2个变量left_hight和right_hight分别代码最左和最右的最大高度
使用2个指针i和k分别从0和n-1的位置开始遍历

如果a[i] < left_hgith && a[i] < right_hight，那么索引为i的位置可以容纳min(left_hight,right_hight)-a[i]的水量
如果a[i] >= left_hight && a[i] <= right_hight，将i右移
如果a[i] >= left_hight && a[i] >= right_hight，将k左移

       
       long 
       
       long 
       
       maxWater(
       
       const 
       
       vector
       
       <
       
       int
       
       > 
       
       &
       
       arr)
       
{
       
       if (
       
       arr.
       
       size() 
       
       <= 
       
       2)
       
  {
       
       return 
       
       0;
       
  }
       
       // 左右双指针
       
       int 
       
       left 
       
       = 
       
       0;
       
       int 
       
       right 
       
       = 
       
       arr.
       
       size() 
       
       - 
       
       1;
       
       // 在[left,right]区间外左边最高、右边最高
       
       int 
       
       left_max 
       
       = 
       
       0;
       
       int 
       
       right_max 
       
       = 
       
       0;
       
       int 
       
       res 
       
       = 
       
       0;
       
       while (
       
       left 
       
       <= 
       
       right)
       
       // 遍历整个数组
       
  {
       
       // 获取短边高度
       
       int 
       
       min_hight 
       
       = 
       
       std::min(
       
       left_max, 
       
       right_max);
       
       res 
       
       += 
       
       std::max(
       
       0, 
       
       min_hight 
       
       - 
       
       std::min(
       
       arr[
       
       left], 
       
       arr[
       
       right]));
       
       // 累加当前索引可以盛水的容量
       
       left_max 
       
       = 
       
       std::max(
       
       left_max, 
       
       arr[
       
       left]);
       
       // 更新左高
       
       right_max 
       
       = 
       
       std::max(
       
       right_max, 
       
       arr[
       
       right]);
       
       // 更新右高
       
       if (
       
       arr[
       
       left] 
       
       < 
       
       arr[
       
       right])
       
       // 更新索引，将较短的那个边往中间移动
       
    {
       
       left
       
       ++;
       
    }
       
       else
       
    {
       
       right
       
       --;
       
    }
       
  }
       
       return 
       
       res;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.