阿里P8跪在了这道题上。。。

[[426900]]

本文转载自微信公众号「高性能架构探索」，作者雨乐。转载本文请联系高性能架构探索公众号。

今年，北京的雨尤其多，淅淅沥沥的。整个中秋节前两天，都是在雨中度过，没了往日中秋节的快乐气氛，幸运的是，在中秋节当天，天气晴朗，算是对整个假期画上了个还算满意的句号。

听着淅淅沥沥的雨声，想起前段时间在脉脉上看了一篇帖子，阿里P8去面试某条，挂在了一面算法上。而自己在3年前面试某公司，也栽在了同样的一道算法上。正所谓吃一堑长一智，把该算法题重新整理了下，分享给大家，希望能够有用。

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

接雨水

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6

解释：上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接6个单位的雨水(蓝色部分表示雨水)

看到题目的第一眼，感觉很简单，但是却不知道从何入手。下面我们将遵循循序渐进的方式，分析此题目的解法。

暴力解法

看到题目的一刻，出于思维定式，必定去查找"凹"型槽的最低部分，然后。。。，如此如此，越来越头大，直至放弃。

我们不妨换个思路，每根柱子上能放多少雨水。那么每根柱子上盛放雨水的高度怎么计算呢?就是其左右两边柱子最大高度的较小者与其高度之差，文字上理解起来比较费力，用图的方式更加便于大家理解。

下面我们将计算柱子坐标(3)-(7)即红框内的盛水量。

我们首先定义4个变量:

  • res 盛水总量，其初始化为0
  • height 当前柱子高度
  • left_max 左边最大高度(包括当前柱子本身
  • right_max 右边最大高度(包括其本身)

首先，计算柱子(3)处其盛水量。其左边最大高度left_max为2，右边最大高度right_max为3，那么横坐标3处盛水量为min(left_max, right_max) - height 赋值之后为min(2, 3) - 2，答案为0，也就是说柱子(3)可盛水量为0。

接着我们计算柱子(4)处盛水量。按照上述计算规则，左边最大高度为2，右边最大高度为3，那么柱子(4)可盛水量为min(2, 3)- 1，答案为1。

然后计算柱子(5)处的盛水量，按照上述计算规则，左边最大高度为2，右边最大高度为3，那么柱子(5)可盛水量为min(2, 3)- 0，答案为2。

然后计算柱子(6)处的盛水量，按照上述计算规则，左边最大高度为2，右边最大高度为3，那么柱子(6)可盛水量为min(2, 3)- 1，答案为1。

最后计算柱子(7)处的盛水量，左边最大高度为3，右边最大高度为3，那么柱子(7)可盛水量为min(3, 3) - 3即0.

因此，柱子(3)到柱子(7)之间所盛水量res = 0 + 1 + 2 + 1 + 0 = 4.

代码实现一：

 
 
 
 
    
  
  
  
  
  1. int trap(vector& height) { 
    2.   
  
  
  
  2.   int res = 0; 
    3.   
  
  
  
  3.    
    4.   
  
  
  
  4.   for (int cur = 0; cur < height.size(); ++cur) { 
    5.   
  
  
  
  5.     int left_max = 0; 
    6.   
  
  
  
  6.     int right_max = 0; 
    7.   
  
  
  
  7.      
    8.   
  
  
  
  8.     // 计算左边最大高度 
    9.   
  
  
  
  9.     for (int left = 0; left <= cur; ++left) { 
    10.   
  
  
  
  10.        left_max = std::max(left_max, height[left]); 
    11.   
  
  
  
  11.     } 
    12.   
  
  
  
  12.      
    13.   
  
  
  
  13.     // 计算右边最大高度 
    14.   
  
  
  
  14.     for (int right = cur; right < height.size(); ++right) { 
    15.   
  
  
  
  15.       right_max = std::max(right_max, height[right]); 
    16.   
  
  
  
  16.     } 
    17.   
  
  
  
  17.      
    18.   
  
  
  
  18.     // 计算总盛水量 
    19.   
  
  
  
  19.     res += std::min(left_max, right_max) - height[cur]; 
    20.   
  
  
  
  20.   } 
    21.   
  
  
  
  21.    
    22.   
  
  
  
  22.   return res; 
    23.   
  
  
  
  23. } 
    24.

上述规则有个trick，就是计算两边最高的时候，都将柱子本身的高度计算在内，这样做是为了在计算盛水量的时候，方便计算。

假设计算柱子(3)，如果在计算两边最大高度的时候不包括柱子(3)本身的高度，那么柱子(3)左边最大高度为1，右边最大高度为3，在计算盛水量的时候，就需要判min(lext_max, right_max)与柱子(3)本身的大小，否则会出现负值，代码实现如下。

代码实现二

 
 
 
 
    
  
  
  
  
  1. int trap(vector& height) { 
    2.   
  
  
  
  2.   int res = 0; 
    3.   
  
  
  
  3.    
    4.   
  
  
  
  4.   for (int cur = 0; cur < height.size(); ++cur) { 
    5.   
  
  
  
  5.     int left_max = 0; 
    6.   
  
  
  
  6.     int right_max = 0; 
    7.   
  
  
  
  7.      
    8.   
  
  
  
  8.     // 计算左边最大高度 
    9.   
  
  
  
  9.     // 注意，与实现一相比，left到cur的前一个截止 
    10.   
  
  
  
  10.     for (int left = 0; left < cur; ++left) { 
    11.   
  
  
  
  11.        left_max = std::max(left_max, height[left]); 
    12.   
  
  
  
  12.     } 
    13.   
  
  
  
  13.      
    14.   
  
  
  
  14.     // 计算右边最大高度 
    15.   
  
  
  
  15.     // 注意，与实现一相比，right从下一个开始 
    16.   
  
  
  
  16.     for (int right = cur + 1; right < height.size(); ++right) { 
    17.   
  
  
  
  17.       right_max = std::max(right_max, height[right]); 
    18.   
  
  
  
  18.     } 
    19.   
  
  
  
  19.      
    20.   
  
  
  
  20.     // 计算总盛水量 
    21.   
  
  
  
  21.     int mx = std::min(left_max, right_max); 
    22.   
  
  
  
  22.     if (mx > height[cur]) { // 需要进行判断 
    23.   
  
  
  
  23.       res += mx - height[cur]; 
    24.   
  
  
  
  24.     } 
    25.   
  
  
  
  25.   } 
    26.   
  
  
  
  26.    
    27.   
  
  
  
  27.   return res; 
    28.   
  
  
  
  28. } 
    29.

暴力解法，理解起来简单，时间复杂度为O(n2),提交之后，毫无疑问会TLE，下面我们从其他方面对暴力法进行优化。

为了便于理解，后面的实现将使用实现二的思想。

动态规划

看了暴力法的实现，我们基本思路已经有了，其时间复杂度为O(n2)，时间主要消耗在查找两边最大柱子高度上。那么有没有什么办法，能够 常数次 遍历就能获取到所有柱子的两边高度呢?

我们仍然以

 
 
 
 
    
  
  
  
  
  1. height = [0,1,0,2,1,0,1,3,2,1,2,1] 
    2.

为例，计算双边最大值。

左侧最大值

定义数组left_max，其中left_max[i]代码第i个柱子左边最大高度。

下面我们来计算柱子左侧的最大高度：

  • 柱子(0)，左侧最大高度为0(其左侧没有柱子)
  • 柱子(1)，左侧最大高度为0(左侧只有柱子0)
  • 柱子(2)，左侧最大高度为1([0 1]数组的最大值)
  • 柱子(3)，左侧最大高度为1([0 1 0]数组最大值)
  • 柱子(4)，左侧最大高度为2([0 1 0 2]数组最大值)
  • 柱子(5)，左侧最大高度为2([0 1 0 2 1]数组最大值)
  • 柱子(6)，左侧最大高度为2([0 1 0 2 1 0]数组最大值)
  • 柱子(7)，左侧最大高度为2([0 1 0 2 1 0 1]数组最大值)
  • 柱子(8)，左侧最大高度为3([0 1 0 2 1 0 1 3]数组最大值)
  • 柱子(9)，左侧最大高度为3([0 1 0 2 1 0 1 3 2]数组最大值)
  • 柱子(10)，左侧最大高度为3([0 1 0 2 1 0 1 3 2 1]数组最大值)
  • 柱子(11)，左侧最大高度为3([0 1 0 2 1 0 1 3 2 1 2]数组最大值)

左侧最大值

从上述规则，我们进行分析，发现有一定的规律可循，即当前柱子左侧最大高度 为 max(上一个柱子左侧最大高度, 上一个柱子高度)。

代码表示如下:

 
 
 
 
    
  
  
  
  
  1. std::vector left_max(height.size(), 0); 
    2.   
  
  
  
  2. for (int i = 1; i < height.size(); ++i) { 
    3.   
  
  
  
  3.   left_max[i] = std::max(left_max[i - 1], height[i]); 
    4.   
  
  
  
  4. } 
    5.

对上述代码进行稍许变化后如下：

 
 
 
 
    
  
  
  
  
  1. std::vector left_max(height.size(), 0); 
    2.   
  
  
  
  2. int mx = 0; 
    3.   
  
  
  
  3. for (int i = 0; i < height.size(); ++i) { 
    4.   
  
  
  
  4.   left_max[i] = mx; 
    5.   
  
  
  
  5.   mx = std::max(mx, height[i]); 
    6.   
  
  
  
  6. } 
    7.

右侧最大值

定义数组right_max，其中left_max[i]代码第i个柱子右边最大高度。

因为要计算右侧最大值，所以必须从最后一个开始向前计算(如果从第一个开始计算的，那么跟暴力法没区别了)。height = [0,1,0,2,1,0,1,3,2,1,2,1]

  • 柱子(11)，右侧最大高度为0(其右侧没有柱子)
  • 柱子(10)，右侧最大高度为1([1]的最大值)
  • 柱子(9)，右侧最大高度为2([2 1]的最大值)
  • 柱子(8)，右侧最大高度为2([1 2 1]的最大值)
  • 柱子(7)，右侧最大高度为2([2 1 2 1]的最大值)
  • 柱子(6)，右侧最大高度为3([3 2 1 2 1]的最大值)
  • 柱子(5)，右侧最大高度为3([1 3 2 1 2 1]的最大值)
  • 柱子(4)，右侧最大高度为3([0 1 3 2 1 2 1]的最大值)
  • 柱子(3)，右侧最大高度为3([1 0 1 3 2 1 2 1]的最大值)
  • 柱子(2)，右侧最大高度为3([2 1 0 1 3 2 1 2 1]的最大值)
  • 柱子(1)，右侧最大高度为3([0 2 1 0 1 3 2 1 2 1]的最大值)
  • 柱子(0)，右侧最大高度为3([1 0 2 1 0 1 3 2 1 2 1]的最大值)

右侧最大值

既然计算出来了双边最大值，那么我们来实现下代码：

 
 
 
 
    
  
  
  
  
  1. int trap(vector& height) { 
    2.   
  
  
  
  2.   int res = 0; 
    3.   
  
  
  
  3.   std::vector left_max(height.size());  
    4.   
  
  
  
  4.   std::vector right_max(height.size());  
    5.   
  
  
  
  5.   int mx = 0; 
    6.   
  
  
  
  6.    
    7.   
  
  
  
  7.   // 循环一、计算左侧最大值 
    8.   
  
  
  
  8.   for (int i = 0; i < height.size(); ++i) { 
    9.   
  
  
  
  9.     left_max[i] = mx; 
    10.   
  
  
  
  10.     mx = std::max(mx, height[i]); 
    11.   
  
  
  
  11.   } 
    12.   
  
  
  
  12.    
    13.   
  
  
  
  13.   mx = 0; 
    14.   
  
  
  
  14.   // 循环二、计算右侧最大值 
    15.   
  
  
  
  15.   for (int i = height.size() - 1; i >= 0; --i) { 
    16.   
  
  
  
  16.     right_max[i] = mx; 
    17.   
  
  
  
  17.     mx = std::max(mx, height[i]); 
    18.   
  
  
  
  18.   } 
    19.   
  
  
  
  19.    
    20.   
  
  
  
  20.   // 循环三、计算所盛雨水量 
    21.   
  
  
  
  21.   for (int i = 0; i < height.size(); ++i) { 
    22.   
  
  
  
  22.     int mn = std::min(left_max[i], right_max[i]); 
    23.   
  
  
  
  23.     if (mn > height[i]) { 
    24.   
  
  
  
  24.       res += mn - height[i]; 
    25.   
  
  
  
  25.     } 
    26.   
  
  
  
  26.   } 
    27.   
  
  
  
  27.    
    28.   
  
  
  
  28.   return res; 
    29.   
  
  
  
  29. } 
    30.

上述代码较暴力方法优化后，时间复杂度优化为O(n), 提交后AE。

动态规划

上述代码中有3个循环，空间复杂度为O(2n)，又作为c++ coder这是不能忍的，能不能再进行优化呢?我们看到循环三单纯为计算盛雨量，能否将循环二和循环3合并，并且优化空间复杂度呢?必须可以，为了阅读起来方便，我们实现代码如下：

 
 
 
 
    
  
  
  
  
  1. int trap(vector& height) { 
    2.   
  
  
  
  2.   int res = 0; 
    3.   
  
  
  
  3.   std::vector v(height.size());  
    4.   
  
  
  
  4.   int mx = 0; 
    5.   
  
  
  
  5.    
    6.   
  
  
  
  6.   // 循环一、计算左侧最大值 
    7.   
  
  
  
  7.   for (int i = 0; i < height.size(); ++i) { 
    8.   
  
  
  
  8.     v[i] = mx; 
    9.   
  
  
  
  9.     mx = std::max(mx, height[i]); 
    10.   
  
  
  
  10.   } 
    11.   
  
  
  
  11.    
    12.   
  
  
  
  12.   mx = 0; 
    13.   
  
  
  
  13.   // 循环二、计算右侧最大值 并 计算盛水量 
    14.   
  
  
  
  14.   for (int i = height.size() - 1; i >= 0; --i) { 
    15.   
  
  
  
  15.     int mn = std::min(mx, v[i]); 
    16.   
  
  
  
  16.     mx = std::max(mx, height[i]); 
    17.   
  
  
  
  17.     if (mn > height[i]) { 
    18.   
  
  
  
  18.       res += mn - height[i]; 
    19.   
  
  
  
  19.     } 
    20.   
  
  
  
  20.   } 
    21.   
  
  
  
  21.    
    22.   
  
  
  
  22.   return res; 
    23.   
  
  
  
  23. } 
    24.

优化后的动态规划

双指针

动态规划方法，时间复杂度和空间复杂度都是O(n)，下面我们介绍一种只有一次循环且空间复杂度为O(1)的算法，这就是双指针算法。

接雨水算法的核心思想，就是计算当前柱子的盛水量，也就是左右两边的最大值的较小者与当前柱子之差。我们先求出数组双端柱子的较小值，然后两边柱子跟这个较小值相比较，如果较小值为左边的柱子，则左边柱子向右移动，直至比当前较小值大。反之，如果较小值为右侧柱子，则右侧柱子向左移动，直至比当前值大。

left 和 right 两个指针分别指向数组的首尾位置，从两边向中间扫描，在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是 left 指向的值，则从左向右扫描，如果较小值是 right 指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，如遇到的值大，则重新确定新的窗口范围，以此类推直至 left 和 right 指针重合

 
 
 
 
    
  
  
  
  
  1. int trap(vector& height) { 
    2.   
  
  
  
  2.   int res = 0; 
    3.   
  
  
  
  3.   int left = 0; 
    4.   
  
  
  
  4.   int right = height.size() - 1; 
    5.   
  
  
  
  5.   while (left < right) { 
    6.   
  
  
  
  6.     int mn = min(height[left], height[right]); 
    7.   
  
  
  
  7.     if (mn == height[left]) { 
    8.   
  
  
  
  8.       ++left; 
    9.   
  
  
  
  9.       while (left < right && height[left] < mn) { 
    10.   
  
  
  
  10.         res += mn - height[left++]; 
    11.   
  
  
  
  11.       } 
    12.   
  
  
  
  12.     } else { 
    13.   
  
  
  
  13.       --right; 
    14.   
  
  
  
  14.       while (left < right && height[right] < mn) { 
    15.   
  
  
  
  15.         res += mn - height[right--]; 
    16.   
  
  
  
  16.       } 
    17.   
  
  
  
  17.     } 
    18.   
  
  
  
  18.   } 
    19.   
  
  
  
  19.   return res; 
    20.   
  
  
  
  20. } 
    21.

单调栈

此种方法较前面的两种(暴力法和双指针法)，如果说前面两种方法都是求每根柱子上盛水量之和的话(即 按列计算)，那么单调栈方法则是 按行计算 每一层的盛水量，如下图所示：

逐层计算

每一行水左右肯定都会被柱子卡住。那么从左向右遍历柱子，如果高度在下降，那么显然不会蓄水。如果高度上升了，那就说明中间是个低点，这之间可以蓄水。而这个下降的高度用单调栈来维护就行了，栈里我们只放下标。

遍历高度，如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意这里不直接把高度压入栈，而是把坐标压入栈，这样方便在后来算水平距离。当遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装雨水。此时栈里至少有一个高度，如果只有一个的话，那么不能形成坑，直接跳过，如果多余一个的话，那么此时把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界，只要取二者较小的，减去坑的高度，长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量。

我们仍然以数组height = [0,1,0,2,1,0,1,3,2,1,2,1]为例来说明单调栈的用法。

假设res初始值为0，用其来计算height数组所表示的柱子高度最大盛水量。

  • 初始化时候，栈为空。

栈为空

  • 因为栈为空，所以下标0入栈，如下图所示：

  • 由于下标1所指向的数组height[1] = 1大于栈顶下标所指向的数，所以下标0出栈，下标1入栈。

  • 由于下标2指向的值小于栈顶值，则下标2入栈。

此时下标指向3，由于下标3指向的值大于栈顶下标指向的值，则出栈，计算增量盛水量((min(2, 1) - 0) * (3 - 1 - 1) = 1)，即增量为1，此时res = 1。

  • 由于下标1所指向的高度小于下标3指向高度，则下标1出栈，此时栈为空，则下标3进栈。

  • 下标4指向的值小于栈顶下标指向的值(1 < 2),下标4入栈

  • 下标5指向的值小于栈顶下标指向的值(0 < 1),下标5入栈

  • 此时下标6指向的值为1，大于栈顶下标所指向的值(1 > 0)，则执行出栈，同时计算盛水增量((min(1, 1) - 0) * (6 - 4 - 1)),增量为1，此时res = 1 + 1 = 2。

  • 下标6所指向的值等于栈顶指向的值(1 = 1),下标6入栈

  • 此时下标指向7，其值大于栈顶值(3 > 1)，则栈顶出栈，计算增量为((min(3, 1) - 1) * (7 - 4 - 1)),增量为0，此时res = 1 + 1 + 0 = 2

  • 此时，下标仍为7，栈顶值为4，由于当前下标指向值大于栈顶指向值，则出栈，计算盛水增量((min(3, 2) - 1) * (7 - 3 - 1)),增量为3，此时res = 1 + 1 + 0 + 3 = 5

计算增量盛水量

  • 此时栈内只有下标3，且其所指向值小于当前下标指向值(2 < 3)，则出栈

下标3出栈

此时栈为空，则下标7入栈

  • 下标8指向值小于栈顶指向值(2 < 3),下标8入栈

  • 下标9指向值小于栈顶指向值(1 < 2),下标9入栈

  • 此时下标为10，其对应值大于栈顶指向值(2 > 1)，则栈顶出栈，并计算增量((min(2, 2) - 1) * (10 - 8 - 1)),增量为1，此时res = 1 + 1 + 0 + 3 + 1 = 6

  • 下标10指向值小于栈顶值，入栈

下标11指向值小于栈顶值，入栈

此时，数组循环结束，尽管栈内还有数，坐标为7 8 10 11，指向的值为3 2 2 1，但其已经不能构成一个凹槽进行盛水，所以算法执行结束。

代码实现如下：

 
 
 
 
    
  
  
  
  
  1. int trap(vector& height) { 
    2.   
  
  
  
  2.   stack st; 
    3.   
  
  
  
  3.   int i = 0, res = 0, n = height.size(); 
    4.   
  
  
  
  4.   while (i < n) { 
    5.   
  
  
  
  5.     if (st.empty() || height[i] <= height[st.top()]) { 
    6.   
  
  
  
  6.     st.push(i++); 
    7.   
  
  
  
  7. } else { 
    8.   
  
  
  
  8.     int t = st.top(); st.pop(); 
    9.   
  
  
  
  9.     if (st.empty()) continue; 
    10.   
  
  
  
  10.     res += (min(height[i], height[st.top()]) - height[t]) * (i - st.top() - 1); 
    11.   
  
  
  
  11.     } 
    12.   
  
  
  
  12.   } 
    13.   
  
  
  
  13.   return res; 
    14.   
  
  
  
  14. } 
    15.

写在最后

架构或者底层原理分析方面，需要调研大量的资料，研究分析源码，很耗费精力。所以后面的文章中，可能会有算法(leetcode经典算法)、面试(针对面试中遇到的一些经典问题)以及架构和底层穿插发表。

 

分享题目：阿里P8跪在了这道题上。。。
本文网址：http://www.shufengxianlan.com/qtweb/news18/479018.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

App设计知识

分类信息网

成都西云机房　　 　成都成品网站　　 　成都定制网站　　 　成都木托盘　　 　明安消防器材　　 　固迪佳新材料　　 　成都网站设计　　 　网站方案　　 　名片印刷　　 　信衡房屋鉴定　　 　香港云主机　　 　达州网站设计　　 　达州服务器托管　　 　成都网站托管　　 　新网创想　　 　成都西云机房　　 　成都宣传画册设计　　 　网站制作报价　　 　四川绵阳主机托管　　 　复盛机电设备安装