拿到华为offer，入职体检不合格。。。

今年一刚毕业的应届毕业生，在去年拿到了华为的offer，结果今年毕业的时候入职体检，术后康复期不合格。

我觉得不去也挺好，祸兮福所倚，福兮祸所伏，就是去了身体也不一定吃的消。保重身体最重要，刚做完手术先把身体养好，以后工作的时间还很长，不差这一年半载。

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

来看下今天的算法题，这题是LeetCode的第84题：柱状图中最大的矩形，难度是困难。

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例1：

输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10

示例2：

输入： heights = [2,4] 输出： 4

• 1 <= heights.length <=10^5

• 0 <= heights[i] <= 10^4

问题分析

这题让计算柱状图所勾勒出的最大矩形面积，在之前我们通过创建笛卡尔树来解决的，今天我们使用单调栈来解决。

单调栈中的元素对应的值从栈底到栈顶是递增的，如果当前元素cur小于栈顶元素 m ，说明栈顶元素 m 遇到了右边比它小的值，那么这个时候栈顶元素 m 出栈。

m 对应的值就是矩形的高度，那么矩形的宽度是多少呢？很明显它就是新的栈顶元素到当前元素cur的距离，因为栈中元素对应的值是递增的，所以新的栈顶元素对应的值就小于 m 。

知道了矩形的高度和宽度就可以计算矩形的面积了，这里我们只需要保存面积的最大值即可。计算完之后如果新的栈顶元素对应的值还小于当前元素cur，还需要继续计算。

JAVA：

public int largestRectangleArea(int[] heights) {     int n = heights.length;     // 元素下标对应的值从栈底到栈顶是递增的     Stack stk =  new Stack<>();     // 第一个柱子的下标是0，默认他前面一个是-1。     stk.push(-1);     int ans = 0;// 记录最大面积     for (int i = 0; i <= n; i++) {         // 当前柱子的高度，如果i == n，表示没有柱子，高度为0。         int curHeight = i == n ? 0 : heights[i];         // 如果当前柱子的高度小于栈顶元素所对应柱子的高度，栈顶元素出栈，计算面积。         while (stk.size() > 1 && curHeight < heights[stk.peek()]) {             int h = heights[stk.pop()];// 出栈的柱子高度             int area = (i - 1 - stk.peek()) * h;// 计算面积             ans = Math.max(ans, area);// 保存最大面积         }         stk.push(i);// 当前柱子的下标入栈     }     return ans;// 返回最大面积。 }

C++：

public:     int largestRectangleArea(vector
               
 &heights) {         int n = heights.size();         // 元素下标对应的值从栈底到栈顶是递增的         stack
                  
 stk;         // 第一个柱子的下标是0，默认他前面一个是-1。         stk.push(-1);         int ans = 0;// 记录最大面积         for (int i = 0; i <= n; i++) {             // 当前柱子的高度，如果i == n，表示没有柱子，高度为 0 。             int curHeight = i == n ? 0 : heights[i];             // 如果当前柱子的高度小于栈顶元素所对应柱子的高度，栈顶元素出栈，计算面积。             while (stk.size() > 1 && curHeight < heights[stk.top()]) {                 int h = heights[stk.top()];// 出栈的柱子高度                 stk.pop();                 int area = (i - 1 - stk.top()) * h;// 计算面积                 ans = max(ans, area);// 保存最大面积             }             stk.push(i);// 当前柱子的下标入栈         }         return ans;// 返回最大面积。     }
         
       

笔者简介

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