专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近一网友在找工作的时候，收到美团的offer，而面试的其他几家还没开奖，所以想在等等，结果美团的offer作废了。offer的确认都是有时效的，给你发了你不确认，人家以为你不打算去了。
面试之后如果手里暂时没有offer，其他几家还不确定的时候，可以先接了，不能太贪，如果觉得不满意，以后还可以再跳槽。给你了你不接，万一后面几个都不发，岂不是一个offer都没了，只能走社招了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第84题：柱状图中最大的矩形。
问题描述
来源：LeetCode第84题
难度：困难
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例1：
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
1 <= heights.length <=10^5
0 <= heights[i] <= 10^4
问题分析
这题让求的是柱状图能勾勒出来的最大矩形面积，因为勾勒出来的最大矩形面积高度肯定是其中某一个柱子的高度，我们可以使用单调栈解决，单调栈存储的是元素的下标， 下标对应的值从栈底到栈顶是单调递增的 。
遍历数组的时候，如果当前元素的值大于等于栈顶元素所对应的值，就把当前元素的下标添加到栈中。如下图，当遍历到前4个元素的时候，因为都是后面一个比前面一个大，所以都压栈，注意压入的是元素下标，不是元素的值。
如果当前元素的值小于栈顶元素，说明栈顶元素遇到了右边比他小的，那么这个栈顶元素左边比他小的是哪个呢？就是它在栈中的下一个元素（也有可能相等，但不影响后面的计算），也就是栈顶元素出栈之后新的栈顶元素。
当我们知道一个柱子左边和右边比他小的，就可以计算以当前柱子为矩形高度所能勾勒出来的最大矩形了。比如上面的图中当指针指向 2 的时候，我们来看下计算步骤。
这里要注意一点的是数组中的第一个元素前面是没有值的，最后一个元素后面也是没有值的，所以我们可以把数组的前面和后面分别添加一个 0 。
JAVA：
public int largestRectangleArea(int[] heights) { Stack
stack = new Stack<>(); // 栈顶到栈底是递减的 // 第一个柱子的下标是0，默认他前面一个是-1。 stack.push(- 1); int maxArea = 0; // 记录最大面积 for ( int i = 0; i <= heights.length; i++) { // 当前柱子的高度，如果i == heights.length，表示没有柱子，高度为0。 int curHeight = i == heights.length ? 0 : heights[i]; // 如果当前柱子的高度小于栈顶元素所对应柱子的高度，栈顶元素出栈，计算面积。 while (stack.size() > 1 && curHeight < heights[stack.peek()]) { int h = heights[stack.pop()]; // 出栈的柱子高度 int area = (i - 1 - stack.peek()) * h; // 计算面积 maxArea = Math.max(maxArea, area); // 保存最大面积 } stack.push(i); // 当前柱子的下标入栈 } return maxArea; // 返回最大面积。 }C++：
public: int largestRectangleArea(vector
&heights) { stack
stk;// 栈顶到栈底是递减的 // 第一个柱子的下标是0，默认他前面一个是-1。 stk.push(-1); int maxArea = 0;// 记录最大面积 for (int i = 0; i <= heights.size(); i++) { // 当前柱子的高度，如果i == heights.length，表示没有柱子，高度为0。 int curHeight = i == heights.size() ? 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;// 计算面积 maxArea = max(maxArea, area);// 保存最大面积 } stk.push(i);// 当前柱子的下标入栈 } return maxArea;// 返回最大面积。 }
Python：
def largestRectangleArea(self, heights: List[int]) -> int: # 第一个柱子的下标是0，默认他前面一个是 - 1。 stk = [-1] # 栈顶到栈底是递减的 maxArea = 0 # 记录最大面积 for i in range(0, len(heights) + 1): # 当前柱子的高度，如果i == heights.length，表示没有柱子，高度为0。 curHeight = 0 if i == len(heights) else heights[i] # 如果当前柱子的高度小于栈顶元素所对应柱子的高度，栈顶元素出栈，计算面积。 while len(stk) > 1 and curHeight < heights[stk[-1]]: h = heights[stk.pop()] # 出栈的柱子高度 area = (i - 1 - stk[-1]) * h # 计算面积 maxArea = max(maxArea, area) # 保存最大面积 stk.append(i) # 当前柱子的下标入栈 return maxArea # 返回最大面积。笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。