指尖划过的轨迹，藏着最细腻的答案~

题目：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

<br>

示例 1: image.png

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

示例 2：

image.png

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

提示：

1 <= heights.length <=10^5 0 <= heights[i] <= 10^4

分析：

首先，面积最大矩形的高度一定是 heights 中的元素。 枚举每个 h = heights[i] 作为矩形的高，那宽我们怎样确定呢？很容易想到左右两边各有一个：

  • 在i的左侧left一定是最近的小于h的下标，如果不存在就为-1；
  • 在i的右侧right一定是最近的小于h的下标，如果不存在就为n；
  • 这样最终的宽就是（right - left - 1）。

为什么这样找的宽会包含在答案中呢？这是因为高h是我们枚举的，所有我们只需要尽可能的保证宽是最大的，就会有最大的答案。

有了宽，那怎样更方便的计算right与left的值呢？可以使用单调栈：栈中的元素是有顺序的。 具体的，我们遍历右边界right，同时维护单调栈——栈中的元素小于heights[right]，对于一个栈顶元素top来说，栈顶的下面一个元素其实就是left，而heights[right] <= heights[top]，所以其实right就是其右边界。

为简化代码逻辑，可以在遍历之前：

  • 把 −1 入栈，当作哨兵。在栈中只有一个数的时候，栈顶的「下面那个数」刚好就是 −1，对应 left[i]=−1 的情况。
  • 往 heights 末尾加一个 −1。如果不加 −1，循环结束的时候，栈中还有数据，这些数据也要计算矩形面积。处理这种情况可以再写一个循环，但更简单的办法是，加一个 −1（或者任意 ≤min(heights) 的数），从而保证循环结束的时候，栈一定是空的（哨兵不算）。

AC代码：

class Solution {
public:int largestRectangleArea(vector<int>& heights) {heights.push_back(-1);int n = heights.size();int ans = 0;stack<int> st; // 单调栈st.push(-1);for (int right = 0; right < n; right++) {while(st.size() > 1 && heights[right] <= heights[st.top()]) {// right 就是比top大的右边的下标int top = st.top(); // 当前正在计算的下标st.pop();int left = st.top(); // 比top小的左边届的下标ans = max(ans, heights[top] * (right - left - 1));}st.push(right);}return ans;}
};