程序员会遇到接雨水吗

一些前言

以前，程序员面试界，有一个传说，叫红黑树

传说，当不想要人时，就和你说，我们来聊聊红黑树吧

但近来，这个地位，渐渐被接雨水☔️取代了

主要是因为，它是字节例行面试题，红黑树可能真是传说，但接雨水是真的会遇到

这不，托了我朋友小云的福，我见识到了接雨水

最近小云在面字节，走到二面，挂了

面试官问，“看过接雨水吗”

“看过”（简单解法）

面试官兴奋起来：”对，字节最喜欢考这个题，我们来写个最优解法吧“

呃，“原来接雨水是真的…“

我没看过接雨水，作为程序员，接雨水也不算一定要会的技能

但事情就离奇在，我是字节的

事情变得有趣了起来

来自接雨水之乡的人，我，不会公司特产🤔

我感觉，我在等待一个时刻，

当我面其它公司，

面试官：既然是字节出来的，那我们先来一道接雨水吧

面试官，ta 可能只是一个正义的人，或可能曾被字节伤过心，但此刻，ta 可以复仇

那么就开始吧，让我搞定它，然后和大家分享我司特产

像解数学题一样写 leetcode

在写题之前，先分享一下我是怎么解题的

我有一套解题范式 SOP （标准操作流程），基本能解决面试题的大半

这主要是由于，以前上数据结构课的时候，每节课都有代码题，解完才放去吃饭，练出来了

我一般把 leetcode 当成数学题解

可以把它理解成计算机专业的数学应用题，只是需要用代码答题

而这应用题，其实只用了大学数学课程里，最简单的部分

对于做题

首先我会思考迭代能不能解，具体有两步：

找到突破口：首先观察遍历条件，找一个能包含所有情况的遍历条件

找到钩子：针对遍历中的单项，找到该情况下的单个结果计算方法

如此，各情况下逐个叠加就可以获得最终结果

像第一点就是概率论思路，简单的排列组合

第二点找到钩子就是考虑观察力，这通常只是一个常识性的问题，或者脑经急转弯的思路

为什么先思考迭代，而不是递归

首先，在面试中会遇到的题，迭代就可以解决大部分

其次，递归层数过深会有栈溢出的风险，不利于 AC

我学数据结构这门课时，老师就说过，所有的递归都能用非递归的方式完成。

而且，迭代比递归更容易优化，容易拿到最优解。

这优化的过程，我通常会思考使用 DP、双指针滑动窗口，来做时间和空间上的优化。

这个流程在解接雨水这道题可谓是体现得淋漓尽致。

接雨水

各位，请看题

42. 接雨水

（难度：困难）

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

假定最大的树是 m

寻找遍历条件

首先，来找一个能遍历所有情况的条件

这样一个二维象限，自然可以用行或用列遍历

按行，粗略看，时间复杂度在O(m * n) ，可能会超时，导致不能 AC，而且优化空间不大

按列，时间复杂度可以控制在O(n * n) 以内，并且有优化的空间

那么选择按列来往下阐述

计算每一种情况

对于列，从观察可以得出：

当一列上方有积水，它的左右必定有比它高的列

而且它的积水高度，和左右两侧最高柱子的高度有关，而且就是两者中较低的那个和自身高度的差值

于是解法就是，针对某一列（高度 X ），计算其左右两侧的最高值（ maxL 和 maxR ）

要是 X 大于其中的任意一个，就说明没积水，继续遍历下一个

要是 X 都小于 L 和 R，那么这一列的积水高度就是 min(maxL，maxR)-X

问题就简化成了，如何求该列左右两侧最高的柱子 maxL 和 maxR

最简单的方法：对于左右两端，逐个比较值大小，求得最大值，那么时间复杂度就是 O(n*n)，空间复杂度是O(1)

因为遍历柱子是一个 n，遍历最大值也是一个 n

对于求最大值，通常可以用动态规划 dp 优化

因为在已经求得前一个柱子左侧最高值 maxL的情况下，求当前柱子左侧最高值只需要比较左侧柱子高度和它的自身高度就可以了。右侧最高值也同理。

所以可以用两个数组 maxLs 和 maxRs 存储

表现在表达式上是这样

maxLs[i] = Max(maxLs[i-1]height[i-1])

maxRs[i] = Max(maxRs[i+1]height[i+1])

这时候，时间复杂度就是 O(n)，空间复杂度也是O(n)

那还有没有更优解呢，让我们来优化下空间

其实我们并不需要记下一个数组，数组中的元素最多也就使用两次，所以可以用双指针来代替

这里的要点是，对于滑动窗口，当从两端逐步向中间前进时，如何获取元素左右两端更低的最高值

已知 heights[1] 左侧最高值是 heights[0]，heights[n-2] 右侧最高值是 heights[n-1]

由此有初始值：left = 1，right = n-2，maxLight = heights[0]，maxRight = heights[n-1]

那么当 heights[0] < heights[n-1] 时

对于 heights[1] 来说右侧最高值必定 ≥ heights[n-1]，于是两侧最高值的较低值就是 heights[0]，就可以计算出自己的积水值，然后 left ++，maxLeft = max(heights[0], heights[1])

当 heights[0] ≥ heights[n-1] 时，heights[n-2]

同理，对于 heights[n-2] 来说左侧最高值必定 ≥ heights[n-1]，于是两侧最高值的较低值就是 heights[n-1]，就可以计算出自己的积水值，然后 right —，maxRight = max(heights[n-2], heights[n-1])

如此向中心推进迭代，迭代次数到达 n-2 时（因为首尾元素积水值必为 0），就可视为完成了最终计算

具体代码如下：


public int trap(int[] heights) {
    int sum = 0;
    int maxLeft = 0;
    int maxRight = 0;
    int left = 1;
    int right = heights.length - 2; 
    for (int i = 1; i < heights.length - 1; i++) {
        //从左到右
        if (heights[left - 1] < heights[right + 1]) {
            maxLeft = Math.max(maxLeft, heights[left - 1]);
            int min = maxLeft;
            if (min > heights[left]) {
                sum = sum + (min - heights[left]);
            }
            left++;
        //从右到左
        } else {
            maxRight = Math.max(maxRight, heights[right + 1]);
            int min = maxRight;
            if (min > heights[right]) {
                sum = sum + (min - heights[right]);
            }
            right--;
        }
    }
    return sum;
}

如此就是最优解，时间复杂度 O(n)，空间复杂度O(1)