精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
最近一网友在找工作的时候，收到美团的offer，而面试的其他几家还没开奖，所以想在等等，结果美团的offer作废了。offer的确认都是有时效的，给你发了你不确认，人家以为你不打算去了。
面试之后如果手里暂时没有offer，其他几家还不确定的时候，可以先接了，不能太贪，如果觉得不满意，以后还可以再跳槽。给你了你不接，万一后面几个都不发，岂不是一个offer都没了，只能走社招了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第84题：柱状图中最大的矩形。
问题描述
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
1 <= heights.length <=10^5
0 <= heights[i] <= 10^4
问题分析
遍历数组的时候，如果当前元素的值大于等于栈顶元素所对应的值，就把当前元素的下标添加到栈中。如下图，当遍历到前4个元素的时候，因为都是后面一个比前面一个大，所以都压栈，注意压入的是元素下标，不是元素的值。
public int largestRectangleArea(int[] heights) {
Stack<Integer> 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;// 返回最大面积。
}
public:
int largestRectangleArea(vector<int> &heights) {
stack<int> 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;// 返回最大面积。
}
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 # 返回最大面积。
