首先引用N大和R大的话。
单调栈：栈中元素单调排列，如果有元素想入栈但不符合单调性，就弹出栈的元素，直到该元素满足栈的单调性再入栈。
用途：求出某元素左边或右边第一个比其大或者小的元素，且时间复杂度O（n）。
单调栈的维护是 O(n) 级的时间复杂度，因为所有元素只会进入栈一次，并且出栈后再也不会进栈了。
例如在：
如果把直方图高度记为数组。面积就等于（左右第一个比自己小的元素到自己的下标差）（自己高度）。
所以问题实质是：找每个元素左右第一个比自己小的元素。所以用到了单调栈。
左侧面积为：入栈后，往栈底方向和相邻元素的下标差自己高度；
右侧面积为：自己被逼出栈时，和逼自己出栈元素下标差*自己高度
原题直方图高度为2, 1, 4, 5, 1, 3, 3，记作数组a[]={2, 1, 4, 5, 1, 3, 3}.拿栈底到栈顶单调增的栈实验：
首先push a[0]=2,a[1]=1想入栈，不满足单调性，要pop a[0]=2，a[0]=2出栈时，在左侧方向，面积为S1=2x1=2；右侧方向面积为S2=2x（下标差1-0）=2。
接着a[2]=4,a[3]=5,满足单调性，正常入栈。此时栈底到栈顶，元素为：a[1],a[2],a[3].当a[4]=1想入栈时，不满足单调性，需要pop a[2]和a[3],pop a[3]时，左侧面积为1x5=5，右侧为1x5=5；pop a[2]时，左侧面积为1x4=4，右侧为2x4=8.
以此类推，最后没有元素了，需要把所有元素依次pop，以记录它们的右侧面积。你可以看做P大说：a[n+1]的位置有一个高度为0的矩形，最后将它加入单调栈时他会将所有矩形都弹出，那么答案也就完成最后的更新了。当然需要用一个变量更新记录面积最大值。
注意：棉花归纳
1.单调栈保存的是每个矩形的编号，也就是位置。
2.在维护单调栈，也就是每个矩形向左向右延伸的过程中会使原来数组的值改变。
3.数据很大，要用long long型。
4.最后一次出栈的栈顶元素就是当前入栈元素可以向左拓展到的最大距离。
#include <string>
#include <iostream>
#include<stack>
using namespace std;
int main()
{
int num;
cout << "请输入直方图组数：";
cin >> num;
int height[1024], temp = 0, result = 0,top=0,sameflag=1;
memset(height, 0, 1024 * sizeof(int));
for(int i=0;i<num;i++)
cin >> height[i];
stack<int> st;//栈用来存数组下标！
height[num] = -1;//最后一个元素为最小值，用于清空栈
for (int i = 0; i < num+1; i++)
{
if (st.empty() || height[i] >= height[st.top()])//如果栈为空或元素大于等于栈顶元素，则入栈，当栈为空，就不用再执行后一句了，此时栈顶指针也没有值。
st.push(i);
else
{
while (!st.empty() && height[i] < height[st.top()])//别忘了栈非空，非空才有栈顶指针。
{
top = st.top();
st.pop();
if(st.empty())//栈底元素
temp = height[top] * (top+i-top-1+1);//出栈元素结算面积，本身高度*（左扩宽度+右扩宽度+本身1）
else if (height[top] == height[top - 1])//有相同元素
{
for (int k = 1; k <top+1; k++)//寻找相同元素个数
{
if (height[top] > height[top - k])
{
sameflag = k;
break;
}
}
temp = height[top] * sameflag;//出栈元素结算面积，本身高度*（左扩宽度+右扩宽度+本身1）
}
else
temp = height[top] * (i - st.top()-1);//出栈元素结算面积，本身高度*（左扩宽度+右扩宽度+1）
if (temp > result)
result = temp;
}
st.push(i);//出了别忘了入栈
}
}
cout << "最大矩形面积为：" << result << endl;
system("pause");
return 0;
}
升级版题目见棉花
#include <string>
#include <iostream>
#include<stack>
#include<vector>
using namespace std;
int main()
{
int row, **matrix = NULL, temp = 0, result = 0, top = 0,sameflag=1;
cout << "请输入行数：";
cin >> row;
vector<string>zq;
string str;
stack<int> st;
for (int i = 0; i < row; i++)
{
cin >> str;
zq.push_back(str);
}
matrix = (int**)malloc(sizeof(int*)*row);
for (int i = 0; i < row; i++)
{
matrix[i] = (int*)malloc(sizeof(int)*(zq[1].size() + 1));//根据输入值动态申请二维数组内存，+1是为了有一个最小元素清空栈
matrix[i][zq[i].size()] = -1;//每行加一个-1，以供清空栈
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < zq[i].size(); j++)
{
matrix[i][j] = zq[i][j] - '0';
if (i > 0)//预处理，第一行照抄，后面每行按规则相加
{
if (matrix[i][j] == 0)
;
else
matrix[i][j] += matrix[i - 1][j];
}
}
}
for (int i = 0; i < row; i++)//一行一行来
{
for (int j = 0; j<zq[1].size() + 1; j++)
{
if (st.empty() || matrix[i][j] >= matrix[i][st.top()])//如果栈为空或元素大于等于栈顶元素，则入栈，当栈为空，就不用再执行后一句了，此时栈顶指针也没有值。
st.push(j);
else
{
while (!st.empty() && matrix[i][j] < matrix[i][st.top()])//别忘了栈非空，非空才有栈顶指针。
{
top = st.top();
st.pop();
if (st.empty())//栈底元素
temp = matrix[i][top] * (top + j - top - 1 + 1);//出栈元素结算面积，本身高度*（左扩宽度+右扩宽度+本身1）
else if (matrix[i][top] == matrix[i][top - 1])//有相同元素
{
for (int k = 1; k <top + 1; k++)//寻找相同元素个数
{
if (matrix[i][top] > matrix[i][top - k])
{
sameflag = k;
break;
}
}
temp = matrix[i][top] * sameflag;//出栈元素结算面积，本身高度*（左扩宽度+右扩宽度+本身1）
}
else//非栈底元素,且左侧无相同元素，只能右扩
temp = matrix[i][top] * (j - st.top()-1);//出栈元素结算面积，本身高度*（左扩宽度+右扩宽度+1）
if (temp > result)
result = temp;
}
if(j!= zq[1].size())//-1不入栈
st.push(j);//出了别忘了入栈
}
}
}
cout << "最大矩形面积为：" << result << endl;
system("pause");
return 0;
}
代码100%通过了牛客Leetcode测试，但和大神的相比简洁性和运行时间还有差距。
看了别人的代码，发现出栈的后两种情况其实可以合并。中间判定代码可以合并成一句代码
sum = max(sum,height[t]*(matrix.empty()?i:i-matrix.top()-1));
整体就简洁多了。
max()、?:等都可以简化代码。简化后：
#include <string>
#include <iostream>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int row, **matrix = NULL, result = 0, top = 0;
cout << "请输入行数：";
cin >> row;
vector<string>zq;
string str;
stack<int> st;
for (int i = 0; i < row; i++)
{
cin >> str;
zq.push_back(str);
}
matrix = (int**)malloc(sizeof(int*)*row);
for (int i = 0; i < row; i++)
{
matrix[i] = (int*)malloc(sizeof(int)*(zq[1].size() + 1));//根据输入值动态申请二维数组内存，+1是为了有一个最小元素清空栈
matrix[i][zq[i].size()] = -1;//每行加一个-1，以供清空栈
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < zq[i].size(); j++)
{
matrix[i][j] = zq[i][j] - '0';
if (i > 0)//预处理，第一行照抄，后面每行按规则相加
{
if (matrix[i][j] == 0)
;
else
matrix[i][j] += matrix[i - 1][j];
}
}
}
for (int i = 0; i < row; i++)//一行一行来
{
for (int j = 0; j<zq[1].size() + 1; j++)
{
if (st.empty() || matrix[i][j] >= matrix[i][st.top()])//如果栈为空或元素大于等于栈顶元素，则入栈，当栈为空，就不用再执行后一句了，此时栈顶指针也没有值。
st.push(j);
else
{
while (!st.empty() && matrix[i][j] < matrix[i][st.top()])//别忘了栈非空，非空才有栈顶指针。
{
top = st.top();
st.pop();
result = max(result, matrix[i][top] * (st.empty() ? j : j - st.top() - 1));
}
if(j!= zq[1].size())//-1不入栈
st.push(j);//出了别忘了入栈
}
}
}
cout << "最大矩形面积为：" << result << endl;
system("pause");
return 0;
}
京公网安备 11010502036488号