单调栈问题集中详解
一、单调栈的定义及特点
所谓的单调栈，就是在栈先进后出的特性之外再添加一个单调的特性，使得栈中元素是递增或者递减的。
其具有以下几个小特点：
1、栈内元素保持单调；
2、每个元素都会入栈并且仅仅入栈一次；
3、栈当中可以直接存储元素本身，也可以存放元素的下标索引(存放索引时是指索引对应的元素是单调的)；
4、对栈的维护工作(以单调递减栈为例，递增栈类似):设当前遍历到的元素是e，如果e大于或者等于栈顶元素，那么就一直弹栈，直到栈顶元素大于e或者栈为空时，再将e入栈；如果小于的话就直接将e入栈即可。
举个简单的小例子，数组如下{3,9,5,2,7,4,6},现在我们维护一个升序栈结构，我们使用0(3)来表示栈中的元素，0是要存入到栈中的索引下标，3表示下标对应的元素。下面来维护这个栈结构，先栈空，直接入栈得到{0(3)},然后遍历到i=1，对应着9，大于栈顶元素就入栈，得到{0(3),1(9)},再接着遍历到i=2，对应着5，小于栈顶元素，出栈，此时栈{0(3)},5大于3，将其进栈，得到{0(3),2(5)},继续遍历到i=3，对应着2，小于栈顶元素，出栈，继续又小于栈顶元素，出栈，这时栈为空，就直接入栈，得到栈{3(2)},继续遍历到i=4，对应着7，大于栈顶元素就直接入栈，得到栈{3(2),4(7)},继续遍历到i=5，对应着4，小于栈顶元素，出栈，接着大于栈顶元素2，就入栈即可，得到栈{3(2),5(4)},继续遍历到i=6，对应元素6，大于栈顶元素，直接入栈捷克，得到栈{3(2),5(4),6(6)}。
当然，我们使用单调栈不是要求最后的栈的结果，而是利用单调栈在添加元素时的特性。观察上面各个阶段的栈内元素，栈顶元素的底下的这一个元素，就是栈顶元素左边第一个小于该栈顶元素的元素，也就是说，当前栈顶元素弹出后，新的栈顶元素是刚刚弹出的那个元素左边第一个小于弹出元素的元素。接着，对于当前要入栈的元素e，如果先弹出栈顶元素才能入栈，说明元素e是栈顶元素右边第一个小于该栈顶元素的元素。
这样我们可以进行一个总结：
1、利用单调递增栈，可以找到栈顶元素左右两边第一个小于该栈顶元素的元素；
2、利用单调递减栈，可以找到栈顶元素左右两边第一个大于该栈顶元素的元素。
典型例题一、单调递增栈的应用——力扣84.柱状图中最大的矩形
题目描述
给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。求在该柱状图中，能够勾勒出来的矩形的最大面积。
思路分析
对于形成的矩形来说，短边会成为矩形高的制约，遍历数组中的元素并维护一个单调递增栈结构来存放下标，当前遍历的元素大于栈顶元素时就直接入栈，小于栈顶元素时就要计算当前面积。这里为了最后能够处理栈中还剩余的元素，我们可以先入栈一个元素-1，这样就可以处理所有元素了。
以[2,1,5,6,2,3]为例，进行分析，maxArea=0,首先入栈-1，得到栈{-1},接着开始遍历元素，i=0时，此时栈中只有一个元素，入栈得到{-1,0(2)},接着i=1时，元素1小于栈顶元素，栈顶元素出栈并计算当前面积curArea=2(1-(-1)-1)=2,现在栈中只有一个元素，入栈，得到{-1,1(1)},接着i=2,大于栈顶元素直接入栈得到{-1,1(1),2(5)},接着i=3，大于栈顶元素直接入栈得到{-1,1(1),2(5),3(6)},接着i=4，对应元素2小于栈顶元素，栈顶元素出栈并计算当前面积curArea=6(4-2-1)=6,maxArea=6,然后栈顶元素还是大于2，栈顶元素继续出栈并计算当前面积curArea=5(4-1-1)=10,maxArea=10,然后栈顶元1小于当前元素2，入栈，得到{-1,1(1),4(2)},继续，i=5，对应元素3大于栈顶元素，入栈{-1,1(1),4(2),5(3)},这样数组元素已经遍历完了，栈中还有元素，那么就继续处理栈中元素，栈顶元素出栈，curArea=3(6-4-1)=3,继续栈顶元素出栈并计算面积，curArea=2(6-1-1)=8,继续栈顶元素出栈并计算面积，curArea=1(6-(-1)+1)=6,这时栈中只有一个元素-1，执行结束。
代码如下
int largestRectangleArea(vector<int>& heights) {
stack<int> st; //使用一个栈来保存下标信息
int len = heights.size();
st.push(-1); //前一个元素的下标
int maxArea = 0, curArea = 0;
for (int i = 0; i<len; ++i)
{
if (st.size() == 1 || heights[st.top()] <= heights[i])
st.push(i); //如果当前元素大于栈顶元素，那么就先入栈
else
{
while (st.size()>1 && heights[st.top()]>heights[i])
{
int top = st.top(); //记录栈顶元素的下标信息
st.pop(); //先将栈顶元素出栈
curArea = (i - st.top() - 1)*heights[top];
maxArea = max(maxArea, curArea);
}
st.push(i);
}
}
while (st.size()>1)
{
int top = st.top();
st.pop();
curArea = (len - st.top() - 1)*heights[top];
maxArea = max(maxArea, curArea);
}
return maxArea;
}高阶扩展例题——力扣85.最大矩形
题目描述
给定一个仅包含0和1、大小为 rows x cols 的二维二进制矩阵，找出只包含1的最大矩形，并返回其面积。
解题思路
这里我们需要求出只包含1的最大矩形面积，当一行一行处理时，第一行对应着[1,0,1,0,0]，这时的最大面积是1，然后加上第二行，对应着数组[2,0,2,1,1],这时的最大面积是3，然后加上第三行，对应着数组[3,1,3,2,2],这时的最大面积是6，然后加上第四行，对应着数组[4,0,0,3,0],这时的最大面积是4，综上可知最大的矩形面积是6.
代码如下
int maximalRectangle(vector<vector<char>>& matrix)
{
if (matrix.size() == 0)
return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> heights(n, 0);
int maxArea = 0, curArea = 0;
for (int j = 0; j<n; ++j)
{
if (matrix[0][j] == '1')
heights[j] = 1;
}
curArea = largestRectangleArea(heights);
maxArea = max(maxArea, curArea);
for (int i = 1; i<m; ++i)
{
for (int j = 0; j<n; ++j)
{
if (matrix[i][j] == '0')
heights[j] = 0;
else
heights[j] += 1;
}
curArea = largestRectangleArea(heights);
maxArea = max(maxArea, curArea);
}
return maxArea;
}
int largestRectangleArea(vector<int>& heights) { //计算最大矩形的面积
stack<int> st; //使用一个栈来保存下标信息
int len = heights.size();
st.push(-1); //前一个元素的下标
int maxArea = 0, curArea = 0;
for (int i = 0; i<len; ++i)
{
if (st.size() == 1 || heights[st.top()] <= heights[i])
st.push(i); //如果当前元素大于栈顶元素，那么就先入栈
else
{
while (st.size()>1 && heights[st.top()]>heights[i])
{
int top = st.top(); //记录栈顶元素的下标信息
st.pop(); //先将栈顶元素出栈
curArea = (i - st.top() - 1)*heights[top];
maxArea = max(maxArea, curArea);
}
st.push(i);
}
}
while (st.size()>1)
{
int top = st.top();
st.pop();
curArea = (len - st.top() - 1)*heights[top];
maxArea = max(maxArea, curArea);
}
return maxArea;
}二、典型例题——力扣42.接雨水
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路分析
要形成存放雨水的局部小容器要满足中间底两边高的条件，这样我们就可以维护一个单调递减栈结构，如果当前元素小于等于栈顶元素，自然右边界就无法得到保证，我们直接入栈保存起来，如果当前元素大于栈顶元素，这时对于栈顶元素来说，左边界由栈里元素保证，右边界由当前遍历到的元素保证，就能够形成一个局部的小容器了。
下面就以数组[0,1,0,2,1,0,1,3,2,1,2,1]作为例子讲解如何求解，Area=0,最开始i=0,入栈得到{0(0)},接着i=1，大于栈顶元素，栈顶元素出栈，这时栈为空，也就是说明刚刚出栈的元素的左边界无法保证，就无法形成容器，将当前遍历到的元素入栈得到栈{1(1)},接着i=2，对应元素0小于栈顶元素，入栈即可，得到栈{1(1),2(0)}，接着i=3，对应元素2大于栈顶元素，出栈，这时栈不为空，说明可以形成局部小容器，计算面积curArea=(3-1-1)(min(height[1],height[3])-height[2])=1*1=1,Area+=curArea=0+1=1;接着栈顶元素小于当前元素，出栈，这时栈空，不需要计算面积，接着将当前元入栈，得到栈{3(2)},接着i=4，对应元素1小于栈顶元素，入栈即可，得到栈{3(2),4(1)},接着i=5，对应元素0小于栈顶元素，入栈即可，得到栈{3(2),4(1),5(0)},接着i=6，对应元素1大于栈顶元素，栈顶元素出栈并计算局部面积curArea=(6-4-1)(min(height[6],height[4])-height[5])=1,Area+=curArea=2;接着栈顶元素1等于当前元素，出栈栈顶元素，然后入栈，得到栈{3(2),6(1)},接着i=7，对应元素3大于栈顶元素，出栈并计算当前局部面积curArea=(7-3-1)(min(3,2)-1)=3,Area+=curArea=2+3=5，继续出栈，这时栈空，那么就将当前元素入栈，得到栈{7(3)},接着i=8，对应元素2小于栈顶元素，入栈，得到栈{7(3),8(2)},接着i=9，对应元素1小于栈顶元素，入栈，得到栈{7(3),8(2),9(1)}，接着i=10，对应元素2大于栈顶元素，出栈并计算当前局部面积curArea=(10-8-1)(min(2,2)-1)=1,Area+=curArea=5+1=6,接着栈顶元素等于当前元素，栈顶元素出栈，然后栈顶元素3大于当前元素，入栈得到栈{7(3),10(2)},接着i=11，对应元素1小于栈顶元素，直接入栈，得到栈{7(3),10(2),11(1)},结束，返回面积6即可。
代码如下
int trap(vector<int>& height)
{
stack<int> st; //维护单调递减栈
int Area = 0;
for (int i = 0; i < height.size(); ++i)
{
while (!st.empty() && height[st.top()] < height[i])
{
int top = st.top();
st.pop();
if (st.empty())
break;
Area += (i - st.top() - 1)*(min(height[i], height[st.top()]) - height[top]);
}
st.push(i);
}
return Area;
}
Soul一面9人在聊