链接: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/.

此题为典型的单调栈问题，目前涉及到的单调栈问题是84（最大矩形）、739（每日温度）。

关于单调栈
单调栈分为单调递增栈和单调递减栈

• 单调递增栈：栈内元素保持单调递增的栈
• 单调递减栈：栈内元素保持单调递减的栈

//单调递增栈 模板
//此处栈中存储的为数
stack<int> st;
for(int i = 0; i < nums.size(); i++)
{while(!st.empty() && st.top() > nums[i]){st.pop();}st.push(nums[i]);
}

单调栈规则及应用
（以单调递增栈为例）

• 栈内的元素是递增的。
• 当栈顶元素出栈时，说明这个新元素是栈顶元素向后找第一个比其小的元素。
• 当栈顶元素出栈后，说明此时的栈顶元素是新元素向前找的第一个比其小的元素。

//栈中存储为数
//向前找到比当前元素第一个小的元素
stack<int> st;
for(int i = 0; i < nums.size(); i++)
{while(!st.empty() && st.top() > nums[i]){st.pop();int first_small=st.top();}st.push(num[i]);
}
return first_small;

题目代码

class Solution {
public:int largestRectangleArea(vector<int>& heights)
{int ans = 0;stack<int> st;heights.insert(heights.begin(), 0);  //在第0个元素后面插入0heights.push_back(0);   //尾部插入0。for (int i = 0; i < heights.size(); i++){while (!st.empty() && heights[st.top()] > heights[i]){/*可以通过使用 * vector.begin() 或 * vector.end() 来获得 vector 中第一个或最后一个的值；也可以直接使用 vector.front() 、vector.back() 来得到 vector 首尾的值。*/int cur = st.top();  st.pop(); int left = st.top() + 1;int right = i - 1;ans = max(ans, (right - left + 1) * heights[cur]);}st.push(i);}return ans;
}
};

【注意】
在数组前后加上0的作用分别对应两种特殊情况：
弹栈的时候，栈为空；
遍历完成以后，栈中还有元素；
详细解释见wei哥解释：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/