HWA08_leetcode85最大矩形

张开发
• 2026/4/9 15:44:25 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

HWA08_leetcode85最大矩形
题目解决方案classSolution:defmaximalRectangle(self,matrix:List[List[str]])-int:#对于每一行来说他们都是一维的heights[0]*len(matrix[0])#记录最大值maxArea0#遍历每一行forrowinrange(len(matrix)):#遍历每一列forcolinrange(len(matrix[0])):#在遍历过程中#如果发现当前位置为1那么把之前记录的1累加下来ifmatrix[row][col]1:heights[col]1else:#一旦发现某个位置为0了那么代表这列的1断掉了需要重置为0heights[col]0#获取当前最大矩形#再更新maxAreamax(maxArea,self.largestRectangleArea(heights))returnmaxAreadeflargestRectangleArea(self,heights:List[int])-int:#初始化结果为0res0#使用单调栈stacklist()#将给定的原数组左右个添加一个0newHeights[0]*(len(heights)2)#左边界为0newHeights[0]0#右边界为0newHeights[len(newHeights)-1]0#其余不变foriinrange(1,len(heights)1):newHeights[i]heights[i-1]#整体思路#对于一个高度如果能得到向左向右的边界#那么就能对每个高度求一次面积#遍历所有高度就能求出最大面积#开始遍历foriinrange(len(newHeights)):# 如果栈不为空且当前考察的元素值⼩于栈顶元素值# 则表示以栈顶元素值为⾼的矩形⾯积可以确定whilestackandnewHeights[i]newHeights[stack[-1]]:#弹出栈元素curstack[-1]stack.pop()#.pop() 是Python中列表list的方法用于移除并返回列表中的一个元素。#获取栈顶元素值对应的高curHeightnewHeights[cur]#栈顶元素弹出后新的栈顶元素就是其左侧边界#leftIndex stack[-1]#栈可能为空leftIndexstack[-1]ifstackelse-1#右侧边界是当前考察的索引rightIndexi#计算矩形宽度curWidthrightIndex-leftIndex-1#计算面积resmax(res,curWidth*curHeight)#当前考察索引入栈stack.append(i)returnres#返回结果函数2见leetcode84图解1找出由1拼成的矩形转化为leetcode84的图像形式图解2注意出现了0代表无法用到转化为leetcode84图解

更多文章