小米不怎么卡学历了，不少双非也都拿到了offer。。。

最近网上有人发文称，小米不怎么卡学历了，身边认识不少双非同学也都拿到了offer，但是薪资就是开的很性价比了。在互联网岗位小米的薪资性价比一直都不是很高。

不过小米现在并不是一家纯互联网公司，除了手机以外还有汽车，我刚在51job上随便看了一下，软件岗位基本上还是本科为主，并没有要求一定是985或211，所以即便是双非院校还是有机会的。

不过小米还有很多专卖店的店长和零售店的店长岗位，要求都是大专学历，如果是在工厂里面估计要求就更低了。

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

来看下今天的算法题，这题是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 个单位的雨水（蓝色部分表示雨水）。

• n == height.length

• 1 <= n <= 2 * 10^4

• 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 ans = 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];// 高度                 ans += w * h;// 存水量累加             }         }         stk.push(i);// 当前柱子的下标入栈     }     return ans; }

C++：

public:     int trap(vector
               
 &height) {         int ans = 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];// 高度                     ans += w * h;// 存数量累加                 }             }             stk.push(i);// 当前柱子的下标入栈         }         return ans;     }
         
       

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。