【力扣日记】84.直方图中最大的矩形暴力枚举——左右端点法（TLE）idea我们暴力尝试所有可能的矩形。由于矩阵是二维图，我们可以用左右端点来唯一标识一个矩阵。所以我们用一个双循环来枚举所有的可能性。矩形的面积等于（右端点坐标-左端点坐标+1）*最小高度，我们遍历的时候顺便查一下。代码类解决方案：deflargestRectangleArea(self,heights:List[int])->int:n,ans=len(heights),0ifn!=0:ans=heights[0]foriinrange(n):height=heights[i]forjinrange(i,n):height=min(height,heights[j])ans=max(ans,(j-i+1)*height)返回ans复杂度分析时间复杂度:$O(N^2)$空间复杂度：$O(1)$暴力枚举——中心扩展法（TLE）思路我们还是暴力尝试所有可能的矩形。只不过我们这次是从中心向两边扩展而已。对于每个i，我们计算左边第一个高度小于它的索引p，并类似地计算右边第一个高度小于它的索引q。那么以i为最低点可以形成的面积为(q-p-1)*heights[i]。这个算法无疑是正确的。我们来证明一下，f(i)代表当i为最低点时可以组成的最大矩阵面积。然后将原问题转化为max(f(0),f(1),f(2),...,f(n-1))。具体算法如下：我们使用l和r数组。l[i]表示左边第一个高度小于它的索引，r[i]表示右边第一个高度小于它的索引。我们从前到后计算l，然后从后到前计算r。再次遍历找到所有可能的区域，并取出最大的一个。代码类解决方案：deflargestRectangleArea(self,heights:List[int])->int:n=len(heights)l,r,ans=[-1]*n,[n]*n,0foriinrange(1,n):j=i-1whilej>=0andheights[j]>=heights[i]:j-=1l[i]=jforiinrange(n-2,-1,-1):j=i+1whilej=heights[i]:j+=1r[i]=jforiinrange(n):ans=max(ans,heights[i]*(r[i]-l[i]-1))returnanscomplexity分析时间复杂度：$O(N^2)$空间复杂度：$O(N)$优化中心扩展法（已接受）思路其实我们的内层循环不需要一步一步来，直接把j-=1改成j=l[j]，j+=1改成j=r[j]就可以了。代码类解决方案：deflargestRectangleArea(self,heights:List[int])->int:n=len(heights)l,r,ans=[-1]*n,[n]*n,0foriinrange(1,n):j=i-1whilej>=0andheights[j]>=heights[i]:j=l[j]l[i]=jforiinrange(n-2,-1,-1):j=i+1whilej=heights[i]:j=r[j]r[i]=jforiinrange(n):ans=max(ans,heights[i]*(r[i]-l[i]-1))returnanscomplexity分析时间复杂度：$O(N)$空间复杂度：$O(N)$monotonestack(accepted)idea实际上，当您读完第二种方法时，您应该已经注意到了。我们的核心是找到左边第一个比i小的和右边第一个比i小的。如果你熟悉单调栈，你应该认为这是一个非常适合使用单调栈的场景。为了简单起见，我在height的首尾添加了两个sentinel元素，这样可以减少额外的边框处理代码。代码类解决方案：deflargestRectangleArea(self,heights:List[int])->int:n,heights,st,ans=len(heights),[0]+heights+[0],[],0foriin范围(n+2):whilestandheights[st[-1]]>heights[i]:ans=max(ans,heights[st.pop(-1)]*(i-st[-1]-1))st.append(i)returnansComplexityAnalysis时间复杂度：$O(N)$空间复杂度：$O(N)$欢迎关注我的公众号《脑洞前端》获取更多新鲜的LeetCode解法
