今年一刚毕业的应届毕业生，在去年拿到了华为的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多题，对算法题有自己独特的解题思路和解题技巧。
热门跟贴