各互联网大厂月薪分布图。。。

专栏：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算法文档 。