求矩形面积问题

力扣84、85

Posted by songjiu on March 22, 2019

题目描述:

来自:https://leetcode-cn.com/problems/largest-rectangle-in-histogram/ 力扣84
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

#题目分析:

暴力遍历法

首先想到的是暴力遍历法,就是遍历该数组的元素,后用left与right指针分别标记该元素的左右位置,left right不断分别向左右移动直到遍历到的元素小于原来元素,则确定了矩形的面积,但是这个方法明显是会超时的,代码如下:

res,temp=0,0
        length=len(heights)
        for i in range(length):
            l=i-1
            r=i+1
            temp=heights[i]
            while (l>=0 and heights[l]>=heights[i]) or (r<length and heights[r]>=heights[i]):
                if l>=0 and heights[l]>=heights[i]:
                    temp+=heights[i]
                    l-=1
                if r<length and heights[r]>=heights[i]:
                    temp+=heights[i]
                    r+=1
            res=max(res,temp)
        return res

升序栈法

刚才的遍历法说明了一个问题,就是一个元素在组成矩形的时候,他的左右边界分别是第一个大于他的元素,借助这个想法,可以用栈的思想,当第一个元素入栈之后,继续遍历,大于他的元素,无法组成他的边界,入栈,此时继续遍历,小于栈顶元素,至少可以组成栈顶元素的右边界,然后持续出栈,直到栈为空(说明当前遍历到的元素是所有栈内元素的右边界),或者直到一个小于该元素的数字成为栈顶,此时再将该元素继续入栈。
那么出栈的元素面积如何计算呢,长x宽,长即为元素的值,宽则为左右边界的差值,右边界,就是将你逼出栈的那个元素的位置,左边界分为两种情况:1.在pop出你之后,栈仍不为空,说明此时栈内有元素比你小,那么你之前的那位的位置就是左边界。2.在pop出你之后,栈为空,由于入栈规则是升序入栈,如果pop你之后栈为空,说明之前从来没有遇到比你小的元素,那么你的左边界就是数组的起点! 注意: 在循环结束之后,你的栈可能非空,此时还要将栈内的元素分别计算一下各自的面积,此时的右边界就是数组的size,左边界仍然如上文所示。
程序如下:

stack = []
        index =  0
        ans = 0
        size = len(heights)
        while index < size:
            if len(stack) == 0 or heights[index] >= heights[stack[-1]]:
                stack.append(index)
                index = index + 1
            else:
                up=heights[stack.pop(-1)]
                if len(stack) == 0:
                    ans = max(ans, up * index)
                else:
                    ans = max(ans, up * (index - stack[-1] - 1))
        while len(stack) != 0:
            up = heights[stack.pop(-1)]
            if len(stack) == 0:
                ans = max(ans, up * size)
            else:
                ans = max(ans, up * (size - stack[-1] - 1))
        return ans

变式

来自力扣85
https://leetcode-cn.com/problems/maximal-rectangle/

变式题目描述

变式分析

可以将该题转换为84,仍然求矩形面积,具体方法为:从上到下依次遍历每行数组,第一次的矩阵为行0,第二次为行0+行1,第三次为行0+行1+行2…..具体的加法类似俄罗斯方块,仅需要考虑新加的一行的数值,如该位置为0,那么这次无法组成一个矩形(相当于没有根基的矩形),新数组的该位设为0,当为1时,新数组为老数组的值+1。之后再调用84的算法即可。

代码如下:

def getmax(self,heights):
        stack = []
        index =  0
        ans = 0
        size = len(heights)
        while index < size:
            if len(stack) == 0 or heights[index] >= heights[stack[-1]]:
                stack.append(index)
                index = index + 1
            else:
                up=heights[stack.pop(-1)]
                if len(stack) == 0:
                    ans = max(ans, up * index)
                else:
                    ans = max(ans, up * (index - stack[-1] - 1))
        while len(stack) != 0:
            up = heights[stack.pop(-1)]
            if len(stack) == 0:
                ans = max(ans, up * index)
            else:
                ans = max(ans, up * (index - stack[-1] - 1))
        return ans
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        import copy
        temp=[]
        result=[]
        if len(matrix)==0:
            return 0
        for i in matrix[0]:
            temp.append(int(i))
        res=[temp]
        for i in range(1,len(matrix)):
            k=copy.deepcopy(temp)
            res.append(k)
            for j in range(len(matrix[0])):
                if matrix[i][j]=='1' :
                    temp[j]+=int(matrix[i][j])
                else:
                    temp[j]=0
        for i in res:
            result.append(self.getmax(i))
        return max(result)