最近网上有人发文称，小米不怎么卡学历了，身边认识不少双非同学也都拿到了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多题，对算法题有自己独特的解题思路和解题技巧。
热门跟贴