给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。
输入 #1
6 2 1 5 6 2 3
输出 #1
10
解释:最大的矩形为图中红色区域,面积为 10
首先第一眼可以看出本题用暴力法一定可以做出来,但纯暴力一般会超时,可以借助单调栈对暴力法进行优化。
先说暴力法,最外层循环遍历 n 根柱子,内部对每根柱子左右分别进行 while 循环找到第一根高度小于当前高度的柱子,就可以算出以当前柱子为高时矩形的最大面积,遍历结束即可找出矩形最大面积。
单调栈法,依旧是最外层循环遍历 n 根柱子,并且只在栈中存储高度递增的柱子的数组下标。比如第 i 根柱子的高度大于栈顶的柱子高度时,就让i入栈,小于栈顶柱子高度,说明以栈顶为高的矩形找到了右边界,而栈中存储的是递增的序列,那么左边界也确定了,左右边界做差就得到了矩形的宽,那么以栈顶为高的矩形的最大面积就确定了,将面积与之前记录的最大面积进行比较,更新最大面积。遍历结束就得到了最终结果。这样就省去了纯暴力中每次循环查找左右边界的过程。光看文字看不懂,这里建议看代码画图自己模拟一遍。
要注意的是最外层遍历要多执行一次,for(int i=0;i<=n;i++),下标为 n 的数组中存柱子高度为0,因为如果出现 n 根柱子高度恰好为递增序列的情况,那么程序不会对最大面积进行更新。
此代码不支持上机检测。
#include<iostream> #include<algorithm> #include<stack> using namespace std; int n; //柱子数量 int max_area; //记录当前最大面积 int area; //记录以当前柱子为高的最大面积 int height[100005]; //存储柱子高度 stack<int> s; //存储高度递增的柱子的数组下标 int main() { cin>>n; for(int i=0;i<n;i++) cin>>height[i]; for(int i=0;i<=n;i++) { while(!s.empty()&&height[s.top()]>height[i]) //栈非空且第i根柱子高度栈顶柱子高度,此时不能入栈,开始计算面积 { if(s.size()==1) area=height[s.top()]; //当栈中仅有一个元素,矩形高为柱子高度宽为1 else area=height[s.top()]*(i-s.top()); //当栈中有多个元素,矩形高为栈顶柱子高度,宽为左右第一个比当前柱子矮的两柱子的间距即i-s.top max_area=max(max_area,area); //与之前记录的最大面积作比较,更新最大面积 s.pop(); //已做过高的柱子出栈 } s.push(i); //栈空或者栈顶柱子高度小于第i根柱子高度,下标入栈 } cout<<max_area; return 0; }