栈是一种后进先出的线性的数据结构，但若在栈的结构之上再规定栈中元素大小需满足单调关系，即成为单调栈。
单调栈分为单调递增栈和单调递减栈：
1. 单调递增栈即栈内元素保持单调递增的栈
2. 单调递减栈即栈内元素保持单调递减的栈
操作规则（以单调递增栈为例）：
1. 如果新的元素比栈顶元素大，就入栈
2. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小
单调栈具有如下性质：
1.栈内元素是递增的
2.当栈中已有元素需要出栈时（遇见了比它小的新元素），说明后续这个新元素是需要出栈的元素向后找第一个比其小的元素
3.当元素出栈后，新栈顶元素是出栈元素向前找第一个比其小的元素
举个例子，现在栈中元素是 2 3 7 。
接下来新元素是4 ，那么在7需要出栈。
当7出栈时，新元素4即为7右边第一个比7小的元素。
当7出栈时，3成为新的栈顶，那么3就是7左边第一个比小的元素。
单调栈可以用\(O(n)\)的复杂度找到序列中第一个大于给定元素的位置和第一个小于（严格来说是小于等于）给定元素的位置。
例题
柱状图中的最大矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
思路
对于每一个矩形，我们需要找到两个边界：第一个高度小于它的右边界和第一个高度小于它的左边界，利用单调栈可以很好的解决这个问题。
class Solution {
public:
int largestRectangleArea(vector<int>& nums)
{
int ans = 0;
//栈中存放的是索引，一定不要搞混淆了
stack<int> st;
//一开始添0，保证在计算过程中，即while循环体内部栈不会变空
nums.insert(nums.begin(),0);
//最后添0，即使给定一个递增序列也可顺利求出
nums.push_back(0);
for(unsigned i = 0; i < nums.size(); i++)
{
while(!st.empty() && nums[i] < nums[st.top()])
{
int temp = st.top();
st.pop();
int width = i - st.top() - 1;
int height = nums[temp];
ans = max(ans, width * height);
}
st.push(i);
}
return ans;
}
};