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

最近在脉脉上看到一张图片，列举了互联网大厂薪资的分布情况，整体来看，多数企业员工薪资集中在 20 - 50K 的区间。 其中贝壳在 30 - 50K 薪资段占比最高，为 72.1% ； 区间50K以上的，字节和拼多多占比最多，都是5.4%，不过我觉得这种统计比较保守了，应该没有算上加班工资，否则只会更高。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第42题：接雨水。

输入 ：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 个单位的雨水（蓝色部分表示雨水）。

输入 ：height = [4,2,0,3,2,5]

输出 ：9

遍历整个数组，如果数组中的某个元素比栈顶元素m大，说明栈顶元素m遇到了右边比他大的值，这个时候栈顶元素m出栈，出栈之后如果栈不为空，那么新的栈顶元素就是左边比他大的值，既然找到左边和右边都比他大的值，就可以计算位置m所能容纳的水了。

注意这里计算某个位置所容纳的水量不是最终的水量，如下图中，c 位置最终容纳的水是 2 ，但我们计算的时候 c 的左边和右边比他大的分别是 b 和 d ，他们的最小高度是 1 ，所以容纳的水也是 1 。

当计算 d 的时候，左右两边比他大（相等也可以）的是 b 和 e ，因为 d 和 b 的高度一样，所以计算容纳水量为 0 。计算 b 的时候，他的左右两边比他大的分别是 a 和 e ，宽度是 3 ，高度是 1 ，容纳的水量是 3 。

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;// 存数量累加