Largest Rectangle in Histogram 直方图的最大正方形

这个算法的思想动态规划  直方体数组 height[ ]

维护一个 栈s，栈里的元素是递增排列的,存的是heigth数组的下标。从左到右扫描height[i]，如果数值大于栈顶的元素，栈中元素出栈，直到栈中元素小于height[i]为止。每次出栈的元素记为last，计算之前的以此为高height[last]的长方体的体积，与最大值比较选取最大值。

这个体积的计算很有讲究，用的是此时栈顶的元素所代表下标(s.top()+1)代表长方体长的开始，长方体长的结束是i 。原因在于s.top()之后的高肯定是大于height[last]的，想清楚了这一点，此题可解。

int largestRectangleArea(vector &height) {stack s;int maxx=0;int len=height.size();for(int i=0;iheight[i]){int last= s.top();s.pop();if(!s.empty()){maxx =max(maxx,(i-s.top()-1)*height[last]);}else{maxx=max(maxx,i*height[last]);}}s.push(i);}while(!s.empty()){int last= s.top();s.pop();if(!s.empty()){maxx =max(maxx,(len-s.top()-1)*height[last]);}else{maxx=max(maxx,len*height[last]);}}return maxx;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！