专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近在脉脉上看到一张图片，列举了互联网大厂薪资的分布情况，整体来看，多数企业员工薪资集中在 20 - 50K 的区间。其中贝壳在 30 - 50K 薪资段占比最高，为 72.1% ；区间50K以上的，字节和拼多多占比最多，都是5.4%，不过我觉得这种统计比较保守了，应该没有算上加班工资，否则只会更高。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第42题：接雨水。
问题描述
来源：LeetCode第42题
难度：困难
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例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 个单位的雨水（蓝色部分表示雨水）。
示例2：
输入：height = [4,2,0,3,2,5] 输出：9
n == height.length
1 <= n <= 2 * 1^04
0 <= height[i] <= 10^5
问题分析
关于接雨水问题我们前面都讲过，有兴趣的可以先看下：
这里再来讲一遍，不过今天的解决方式和之前的不一样，今天使用的是 单调栈 来解决。
如果要计算某个位置是否能接雨水，需要找到这个位置左边和右边有没有比他高的柱子，如果有，那么该位置肯定是能接的。所以我们可以使用一个单调栈，从 栈顶到栈底是单调递增的 。
遍历整个数组，如果数组中的某个元素比栈顶元素m大，说明栈顶元素m遇到了右边比他大的值，这个时候栈顶元素m出栈，出栈之后如果栈不为空，那么新的栈顶元素就是左边比他大的值，既然找到左边和右边都比他大的值，就可以计算位置m所能容纳的水了。
注意这里计算某个位置所容纳的水量不是最终的水量，如下图中，c 位置最终容纳的水是 2 ，但我们计算的时候 c 的左边和右边比他大的分别是 b 和 d ，他们的最小高度是 1 ，所以容纳的水也是 1 。
当计算 d 的时候，左右两边比他大（相等也可以）的是 b 和 e ，因为 d 和 b 的高度一样，所以计算容纳水量为 0 。计算 b 的时候，他的左右两边比他大的分别是 a 和 e ，宽度是 3 ，高度是 1 ，容纳的水量是 3 。
JAVA：
public int trap(int[] height) { int water = 0;// 容纳的水量 // 单调栈，存放的是柱子的下标，从栈顶到栈底是递增的。 Stack
stk = new Stack<>(); for ( int i = 0; i < height.length; i++) { // 如果栈不为空，并且当前元素比栈顶元素大 while (!stk.isEmpty() && height[i] > height[stk.peek()]) { int index = stk.pop(); // 栈顶元素出栈。 // 因为栈从顶到底是递增的，此时如果栈不为空，说明在数组中index左边还有比他高的柱子。 if (!stk.isEmpty()) { int left = stk.peek(); // 左边界 int w = i - left - 1; // 宽度 int h = Math.min(height[left], height[i]) - height[index]; water += w * h; // 存数量累加 } } stk.push(i); } return water; }C++：
public: int trap(vector
&height) { int water = 0;// 容纳的水量 // 单调栈，存放的是柱子的下标，从栈顶到栈底是递增的。 stack
stk; for (int i = 0; i < height.size(); i++) { // 如果栈不为空，并且当前元素比栈顶元素大 while (!stk.empty() && height[i] > height[stk.top()]) { int index = stk.top(); stk.pop();// 栈顶元素出栈。 // 因为栈从顶到底是递增的，此时如果栈不为空，说明在数组中index左边还有比他高的柱子。 if (!stk.empty()) { int left = stk.top();// 左边界 int w = i - left - 1;// 宽度 int h = min(height[left], height[i]) - height[index]; water += w * h;// 存数量累加 } } stk.push(i); } return water; }
C：
#define min(a, b) (((a) < (b)) ? (a) : (b)) int trap(int *height, int heightSize) { int water = 0;// 容纳的水量 // 单调栈，存放的是柱子的下标，从栈顶到栈底是递增的。 int *stk = malloc(20000 * sizeof(int)); int top = 0;// 栈顶 for (int i = 0; i < heightSize; i++) { // 如果栈不为空，并且当前元素比栈顶元素大 while (top != 0 && height[i] > height[stk[top - 1]]) { int index = stk[--top];// 栈顶元素出栈。 // 因为栈从顶到底是递增的，此时如果栈不为空，说明在数组中index左边还有比他高的柱子。 if (top != 0) { int left = stk[top - 1];// 左边界 int w = i - left - 1;// 宽度 int h = min(height[left], height[i]) - height[index]; water += w * h;// 存数量累加 } } stk[top++] = i; } return water; }Python：
def trap(self, height: List[int]) -> int: water = 0 # 容纳的水量 # 单调栈，存放的是柱子的下标，从栈顶到栈底是递增的。 stk = [] for i, num in enumerate(height): # 如果栈不为空，并且当前元素比栈顶元素大 while stk and num > height[stk[-1]]: index = stk.pop() # 栈顶元素出栈。 # 因为栈从顶到底是递增的，此时如果栈不为空，说明在数组中index左边还有比他高的柱子。 if stk: left = stk[-1] # 左边界 w = i - left - 1 # 宽度 h = min(height[left], num) - height[index] water += w * h # 存数量累加 stk.append(i) return water笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴