做防水怎样注册网站,深圳深度网站建设,如何在手机上设计房屋装修效果图,seo外包优化公司柱状图中最大的矩形
题目 分析
矩形的面积等于宽乘以高#xff0c;因此只要能确定每个矩形的宽和高#xff0c;就能计算它的面积。如果直方图中一个矩形从下标为 i 的柱子开始#xff0c;到下标为 j 的柱子结束#xff0c;那么这两根柱子之间的矩形#xff08;含两端的柱…柱状图中最大的矩形
题目 分析
矩形的面积等于宽乘以高因此只要能确定每个矩形的宽和高就能计算它的面积。如果直方图中一个矩形从下标为 i 的柱子开始到下标为 j 的柱子结束那么这两根柱子之间的矩形含两端的柱子的宽是 j-i1矩形的高就是两根柱子之间的所有柱子最矮的高度。
暴力解法不可取 如果能逐一找出直方图中所有矩形并比较它们的面积就能够得到最大矩形的面积。方法为采用嵌套的二重循环遍历所有矩形并比较他们的面积。该种方法的时间复杂度为O(N^2)根据题目所给的提示可知这种方法不能解决本题会超时。
代码为
class Solution {
public:int largestRectangleArea(vectorint heights) {int nheights.size();int maxarea0;for(int i0;in;i){int minheightheights[i];for(int ji;jn;j){minheightmin(minheight,heights[j]);int areaminheight*(j-i1);maxareamax(maxarea,area);}}return maxarea;}
};
分治法本题不可取 仔细观察直方图可以发现这个直方图的最大矩形有3中可能 第一种矩形通过直方图中最矮的柱子 第二种矩形的起始柱子和终止柱子都在直方图中最矮柱子的左侧 第三种矩形的起始柱子和终止柱子都在直方图中最矮柱子的右侧。 第二种和第三种从本质上来说和求整个直方图的最大矩形面积是同一个问题可以用递归函数解决。
代码为
class Solution {
public:int largestRectangleArea(vectorint heights) {return helper(heights,0,heights.size()-1);}int helper(vectorint heights,int start,int end){if(startend) return 0;else if(startend) return heights[start];else{int minindexstart;for(int istart1;iend;i){if(heights[i]heights[minindex])minindexi;}int area(end-start1)*heights[minindex];int lefthelper(heights,start,minindex-1);int righthelper(heights,minindex1,end);return max(area,max(left,right));}}
};
单调栈法可取 下面介绍一种非常高效巧妙的解法。这种解法用一个栈保存直方图的柱子并且在栈中的柱子的高度是递增排序的。为了方便计算矩阵的高度栈中保存的是柱子在数组中的下标可以根据下标得到柱子的高度。 这种解法的基本思想是确保保存在栈中的直方图的柱子的敢赌是递增排序的。假设从左到右逐一扫描数组中的每根柱子如果当前柱子的高度大于位于栈顶柱子的高度那么将该柱子的下标入栈否则将位于栈顶的柱子的下标出栈并且计算以位于栈顶的柱子为顶的最大矩形的面积。【注意此时出栈须满足栈不为空并且栈顶柱子的高度大于等于当前柱子的高度】 以某根柱子为顶的最大矩形一定是从该柱子向两侧眼神知道遇到比它矮的柱子这个最大矩形的高是该柱子的高最大矩形的宽是两侧比它矮的柱子中间的间隔。 如果当前扫描到的柱子的高小于位于栈顶柱子的高那么将位于栈顶的柱子的下标出栈并且计算以位于栈顶的柱子为顶的最大矩形的面积。由于保存在栈中的柱子的高度是递增排序的因此栈中位于栈顶前面的一根柱子一定比位于栈顶的柱子矮于是很容易就能找到位于栈顶的柱子两侧比它矮的柱子。 当计算以当前柱子为顶的最大矩形的面积时如果栈中没有柱子那么意味着它左侧的柱子都比它高因此可以想象在下标为 -1 的位置有一根比它矮的柱子。 当扫描数组中所以柱子之后栈中可能仍然剩余一些柱子。因此需要注意将这些柱子的下标出栈并计算以它们为顶的最大矩形的面积。 在扫描完数组中所有的柱子之后当计算以当前柱子为顶的最大矩形的面积时说明它的右侧没有比它矮的柱子如果一根柱子的右侧有比它矮的柱子那么当扫描到右侧较矮柱子的时候他就已经出栈了。因此可以想象下标为数组长度的位置有一根比它矮的柱子。 由于已经计算了以每根柱子为顶的最大矩形面积因此比较这些矩形的面积就能得到脂肪图中的最大矩形面积。
代码为
class Solution {
public:int largestRectangleArea(vectorint heights) {int nheights.size();stackint st;st.push(-1);int maxarea0;for(int i0;in;i){while(st.top()!-1 heights[st.top()]heights[i]){int heightheights[st.top()];st.pop();int widthi-st.top()-1;maxareamax(maxarea,height*width);}st.push(i);}while(st.top() ! -1){int heightheights[st.top()];st.pop();int widthn-st.top()-1;maxareamax(maxarea,height*width);}return maxarea;}
};
最大矩形
题目 分析 上一道题是关于最大矩形的这道题也是关于最大矩形的他们之间有没有某种联系如果能从矩阵中找出直方图那么就能通过计算直方图中的最大矩形面积来计算矩阵中的最大矩形面积。 直方图是由排列在同一基线上的相邻柱子组成的图形由于题目要求矩形中只包含数字1因此将矩阵中上下相邻的值为1的各自看成直方图中的柱子如果分别以矩阵的每行为基线就可以得到若干行由数字1的格子组成的直方图。如下图所示
对应的直方图如下 说明a以矩阵第一行为基线的直方图b以矩阵第二行为基线的直方图c以矩阵第三行为基线的直方图d以矩阵第四行为基线的资方图。
暴力解法可取
class Solution {
public:int maximalRectangle(vectorstring matrix) {if(matrix.size()0 || matrix[0].size()0) return 0;int mmatrix[0].size();vectorint v(m);int mxarea0;for(string s:matrix){for(int i0;im;i){if(s[i]0) v[i]0;else v[i];}mxareamax(mxarea,maxarea(v));}return mxarea;}int maxarea(vectorint heights) {int nheights.size();int maxarea0;for(int i0;in;i){int minheightheights[i];for(int ji;jn;j){minheightmin(minheight,heights[j]);int areaminheight*(j-i1);maxareamax(maxarea,area);}}return maxarea;}
};
分治法可取
class Solution {
public:int maximalRectangle(vectorstring matrix) {if(matrix.size()0 || matrix[0].size()0) return 0;int mmatrix[0].size();vectorint v(m);int mxarea0;for(string s:matrix){for(int i0;im;i){if(s[i]0) v[i]0;else v[i];}mxareamax(mxarea,maxarea(v));}return mxarea;}int maxarea(vectorint heights) {return helper(heights,0,heights.size()-1);}int helper(vectorint heights,int start,int end){if(startend) return 0;else if(startend) return heights[start];else{int minindexstart;for(int istart1;iend;i){if(heights[i]heights[minindex])minindexi;}int area(end-start1)*heights[minindex];int lefthelper(heights,start,minindex-1);int righthelper(heights,minindex1,end);return max(area,max(left,right));}}
};
单调栈法可取
class Solution {
public:int maximalRectangle(vectorstring matrix) {if(matrix.size()0 || matrix[0].size()0) return 0;int mmatrix[0].size();vectorint v(m);int mxarea0;for(string s:matrix){for(int i0;im;i){if(s[i]0) v[i]0;else v[i];}mxareamax(mxarea,maxarea(v));}return mxarea;}int maxarea(vectorint v){stackint st;st.push(-1);int area0;for(int i0;iv.size();i){while(st.top()!-1 v[i]v[st.top()]){int heightv[st.top()];st.pop();int widthi-st.top()-1;areamax(area,height*width);}st.push(i);}while(st.top()!-1){int heightv[st.top()];st.pop();int widthv.size()-st.top()-1;areamax(area,height*width);}return area;}
};
