最大矩形面积 (赛博朋克版) —— 单调栈经典两次遍历法

题目描述赛博朋克巨幅霓虹广告【题目背景】在霓虹闪烁的夜之城林立的高楼大厦构成了一道参差不齐的城市天际线。为了迎接即将到来的“星际狂欢节”超级巨头“荒坂科技”计划在市中心的一排建筑外墙上挂起一块史无前例的巨幅矩形全息霓虹广告牌。【题目详情】市中心共有n栋紧挨着的大楼排成一列。已知第i栋大楼的高度为h[i]。每栋大楼的宽度均可以视为1。为了保证广告牌的平整和安全这块巨幅矩形广告牌必须紧贴着大楼的表面安装且广告牌的任何部分都不能超出其所覆盖大楼的高度也就是说如果广告牌跨越了多栋大楼它的最高点受限于这些大楼中最矮的那一栋。请计算出这块全息霓虹广告牌的最大可能面积。【输入格式】第一行包含一个整数n表示大楼的总数。 第二行包含n个整数h[1],h[2], ..., h[n]相邻两个数之间用单个空格隔开表示从左到右每栋大楼的高度。【输出格式】输出一行包含一个整数表示这块全息霓虹广告牌的最大可能面积。【样例输入】7 2 4 4 6 4 3 1【样例输出】16【样例解释】选择第 2、3、4、5 栋大楼它们的高度分别是 4, 4, 6, 4。如果广告牌跨越这四栋大楼高度最高只能取决于最矮的大楼高度为4。 此时广告牌的宽度为4高度为4总面积为 4*416。这是所有可能方案中面积最大的一种。(注如果选第1到6栋大楼高度受限于最矮的 2宽度为6面积为12不如16 大。)【数据范围】对于100%的数据保证1n 2000001h[i] 10^9。题目分析本题是一道非常经典的算法题同 LeetCode 84柱状图中最大的矩形。核心切入点任何一个矩形它的高度一定是由构成这个矩形的最矮的那根柱子决定的。 因此我们可以转换思路枚举每一根柱子假设它是最终矩形中最矮的那根即矩形的高度就是这根柱子的高度那么这个矩形能向左、向右延伸多远向右延伸的极限遇到右边第一个比它矮的柱子就得停下。向左延伸的极限遇到左边第一个比它矮的柱子就得停下。只要帮每根柱子找到这两个边界算出宽度再乘以它自己的高度就能求出以它为高度的最大面积。最后在所有柱子算出的面积中取最大值即可。思考过程与算法设计为了逻辑最清晰、最不易出错我们采用单调栈的两次遍历策略第一步从左向右扫描找右边界r[i]维护一个存储下标的单调栈栈底到栈顶对应的高度严格递增。当遍历到第i根柱子时如果它的高度小于栈顶柱子的高度说明第i根柱子就是栈顶柱子“右边第一个比它矮的”。记录r[s.top()]i并将栈顶弹出。遍历结束后栈里剩余元素的右边界假定在数组最右侧的外面即n1。第二步从右向左扫描找左边界l[i]清空栈使用完全相同的逻辑只不过循环方向变成从n到1。如果当前柱子矮于栈顶说明当前柱子是栈顶柱子“左边第一个比它矮的”。记录l[s.top()]i。遍历结束后栈里剩余元素的左边界假定在数组最左侧的外面即0。第三步计算面积遍历所有柱子计算以第i根柱子为高的矩形宽度宽度r[i]-l[i]- 1。计算面积并更新全局最大值。时空复杂度分析时间复杂度O(n)。寻找右边界时每根柱子最多入栈一次、出栈一次寻找左边界时同理。两次遍历的总操作次数与n呈线性关系。最后的面积计算也是O(n)。空间复杂度O(n)。使用了三个大小为n的数组h,l,r以及一个单调栈空间占用随n线性增长。易错点总结溢出题目中高度最大可达10^9宽度最大可达200000。最坏情况下最大面积为2* 10^14这远远超过了32位int的上限约2.1*10^9。高度数组h和记录最大面积的变量ma必须使用long long。边界的设定宽度计算公式是r[i]-l[i]-1。为了保证公式在找不到更矮柱子时依然成立必须将找不到右边界的r设为n1找不到左边界的l设为0。完整代码//最大矩形面积 #include iostream #include stack #include algorithm//对应max using namespace std; int n; long long h[200010];//每一列格子涂色的高度 stackint s;//单调栈 存放下标 int l[200010];//l[i]代表i左边第一个高度小于它的格子的下标 int r[200010];//r[i]代表i右边第一个高度小于它的格子的下标 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; for(int i1;in;i) cinh[i]; //先找每个格子右边第一个高度小于它的格子的下标 for(int i1;in;i){ //如果栈非空 且当前格子高度矮于栈顶格子 while(!s.empty()h[i]h[s.top()]){ r[s.top()]i;//栈顶格子右边第一个比栈顶格子矮的格子的下标记录下来 s.pop();//栈顶格子出栈 } //当栈为空或当前格子高度大于等于栈顶格子 //入栈 s.push(i); } //栈内最后剩下的格子都是右边没有比他们矮的格子所以记录为n1最后一个格子后面 while(!s.empty()){ r[s.top()]n1; s.pop(); } //先找每个格子左边第一个高度小于它的格子的下标 for(int in;i1;i--){ //如果栈非空 且当前格子高度矮于栈顶格子 while(!s.empty()h[i]h[s.top()]){ l[s.top()]i;//栈顶格子左边第一个比栈顶格子矮的格子的下标记录下来 s.pop();//栈顶格子出栈 } //当栈为空或当前格子高度大于等于栈顶格子 //入栈 s.push(i); } //栈内最后剩下的格子都是左边没有比他们矮的格子所以记录为0第一个格子前面 while(!s.empty()){ l[s.top()]0; s.pop(); } long long ma0;//记录最大面积 //遍历所有各自计算最大面积 for(int i1;in;i){ mamax(ma,(r[i]-l[i]-1)*h[i]); } coutma; return 0; }