字节跳动编程题——接雨水

微信公众号：编程笔记本

点击上方蓝字关注我，我们一起学编程
欢迎小伙伴们分享、转载、私信、赞赏

今天我们一起来探讨一道字节跳动的算法面试题——接雨水。

题目：有一组不同高度的台阶，由一个整数数组表示，数组中每个元素代表台阶的高度。当开始下雨了（雨水足够多），台阶之间的水坑会积多少水呢？如下图所示，可以表示为数组 [0,1,0,2,1,0,1,3,2,1,2,1] ，程序返回积水量 6 。

图片

这道题十分有趣，解法也很多样。主要有暴力法、记忆法、双指针法等几种，下面我们一一探讨。

一、暴力法

当我们一开始拿到题目的时候，可能并没有什么好的思路，那么这时候我们可以不去考虑整体的情况，可以先从局部下手。具体来说就是，仅仅针对位置 i ，此处能积多少水呢？

图片

很显然，位置 i 处能积 2 格水。为什么刚好能积 2 格水呢？原来，位置 i 的高度为 0 ，其左边最高的台阶为 2 ，右边最高的台阶为 3 ，根据木桶效应，此处最大的积水高度为 min(2, 3) - 0 。

图片

更一般地描述可以概括为下面的公式：
积水高度[i] = min(i左侧最高台阶, i右侧最高台阶) - 台阶高度[i];

也就是说，我们要计算出位置 i 的积水高度，就必须要知道位置 i 左侧的最高台阶高度和位置 i
右侧的最高台阶高度。分析到这里，暴力法就自然引出了，下面是参考代码：

int trap(vector<int>& height)
{int ans = 0;int n = height.size();// 第一个台阶和最后一个台阶不会积水for (int i = 1; i < n - 1; ++i){int l_max = 0;int r_max = 0;// 右边最高高度for (int j = i + 1; j < n; ++j){if (height[j] > r_max){r_max = height[j];}}// 左边最高高度for (int j = i - 1; j >= 0; --j){if (height[j] > l_max){l_max = height[j];}}// 累加积水量ans += min(l_max, r_max) - height[i];}return ans;}

这个算法简单粗暴，但童话里“大力出奇迹”都是骗人的，容易知道，暴力法的时间复杂度为 O(n^2) ，空间复杂度为 O(1)。

O(n^2) 的复杂度可不是什么好主意。反观上面的暴力法，我们会发现，在每个位置处都要计算其左右最高台阶高度，而在寻找最高台阶的过程中，有大量的计算是重复的。

所以一种很自然的思路就出现了：用空间换时间，这就是下面将要介绍的记忆法。

二、记忆法

有了上面的经验，为了避免多余的重复计算，我们可以把每个位置的左右最高台阶高度记录下来，这样就不必在每个位置处都进行遍历操作了，时间复杂度自然就下来了。

为此，我们使用两个数组来存储左右最高台阶高度：l_max, r_max 。l_max[i] 表示位置 i 左侧最高台阶高度， r_max[i] 表示 位置 i 右侧最高台阶高度。

我们事先将这两个数组准备好，避免多余的重读计算。下面是记忆法的参考代码：

int trap(vector<int>& height)
{int ans = 0;int n = height.size();vector<int> l_max(n);vector<int> r_max(n);l_max[0] = height[0];r_max[n - 1] = height[n - 1];// 准备 l_maxfor (int i = 1; i < n; ++i){l_max[i] = max(height[i], l_max[i - 1]);}// 准备 r_maxfor (int i = n - 2; i >= 0; --i){r_max[i] = max(height[i], r_max[i + 1]);}// 计算积水量for (int i = 1; i < n - 1; ++i){ans += min(l_max[i], r_max[i]) - hright[i];}return ans;}

现在的算法，时间复杂度为 O(n) ，空间复杂度为 O(n)。显然，时间复杂度已经最优了，但这是以 O(n) 的空间复杂度换来的结果。

有没有一种时间复杂度为 O(n) ，空间复杂度为 O(1) 的解法呢？那就是下面将要介绍的双指针法啦！

三、双指针法

之所以记忆法需要 O(n) 的空间复杂度，是因为我们保存了左右最高台阶的高度，我们想砍掉这个 O(n) 空间，一个自然的想法就是随机应变，边走边算。

首先来看一部分代码：

int trap(vector<int>& height)
{int ans = 0;int n = height.size();int l_max = height[0];int r_max = height[n - 1];while (left <= right){l_max = max(l_max, height[left]);r_max = max(r_max, height[right]);++left;--right;}......
}

在上面的代码中，l_max 和 r_max 分别代表着什么呢？

通过分析代码容易知道，l_max 表示 height[0…left] 中最高台阶的高度，r_max 表示 height[right…(n-1)] 中最高台阶的高度。

同样地，我们将前面的公式复写在此：
积水高度[i] = min(i左侧最高台阶, i右侧最高台阶) - 台阶高度[i];

要计算某位置处的积水高度，需要知道该位置左右两侧的最高台阶高度，而我们现在只计算了位置 left 左侧的最高台阶高度和 位置 right 右侧的最高台阶高度，这样的出来的结果正确吗？

我们来看一下下面的例子

图片

我们要计算位置 left 的积水高度，现在我们知道了位置 left 左侧的最高台阶高度为 1 ，right 右侧的最高台阶高度为 2 ，此时我们计算出位置 left 处的积水高度为 1 ，这与拥有信息“位置 left 右侧的最高台阶高度为 3” 时计算的结果一致。

那上面的情况是偶然现象吗？

当然不是，这就要回到我们一开始提到的木桶效应了。原来，不管位置 left 右侧的最高台阶高度是多少，只要我得出了右侧的某一较高位置（对应于局部的 right…(n-1)），这个高度与当前高度能够形成坑，那么 OK ，我就可以确定在此处能够积水，并且积水的高度与较低的台阶高度有关，而与较高或者更高的台阶高度无关，这就是为什么双指针法只计算了部分的高度就能够得到全局解的原因。

分析到这里，双指针法就介绍完毕了，下面是参考代码：

int trap(vector<int>& height)
{int ans = 0;int n = height.size();int l_max = height[0];int r_max = height[n - 1];while (left <= right){l_max = max(l_max, height[left]);r_max = max(r_max, height[right]);// 每次较低台阶的指针移动一格if (l_max <= r_max){ans += l_max - height[left];++left;}else{ans += r_max - height[right];--right;}}return ans;
}

好啦，时间复杂度为 O(n) ，空间复杂度为 O(1) 的愿望已经实现啦，目前的解法算是比较优（不敢说最优）了，小伙伴们，你们有更优的解法，欢迎私信与我分享！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！