https://leetcode-cn.com/probl...会超时的方法：双循环最简单的思路，时间复杂度O(n^2)会超时out（超时代码附在最后）。分而治之算法首先找到当前数组中的最小元素。那么答案就会分以下三种情况：包含最小元素，那么height就是最小元素的高度，length就是整个区间不包含最小元素，不包含最小元素就底部元素的左侧（递归左半区间），并且在底部的下一个元素有一条边（递归右半区间）。这种方法的平均时间复杂度是O(nlogn)，但是最坏情况的时间复杂度还是O(n^2)，同样会超时（超时代码附在文末）。正确的解决方案是从正向遍历之后，过程中维护一个增量栈。如果下一个元素大于栈顶元素，则直接压入栈中。如果小于，则栈中的大元素全部出栈，计算出的高度为出栈元素的高度，宽度介于当前元素和栈顶元素之间。为什么弹出元素的高度可以作为高度，当前位置到栈顶元素位置的距离可以作为宽度？因为栈是递增的，低于弹出元素高度的元素一定在栈中，而栈顶一定是离这个元素最近的（高度小于这个元素的元素）。也就是说，它们之间的元素的高度要大于这个元素。类解决方案：deflargestRectangleArea(self,heights:List[int])->int:hs=[0]+heights+[0]s=[]ans=0fori,hinenumerate(hs):whilesandhs[s[-1]]>h:j=s.pop()ans=max(ans,hs[j]*(i-s[-1]-1))s.append(i)returnans超时代码超时代码一双重循环类解决方案：deflargestRectangleArea(self,heights:List[int])->int:maxa=0foriinrange(len(heights)):minh=heights[i]forjinrange(i,len(heights)):minh=min(minh,heights[j])maxa=max(maxa,minh*(j-i+1))returnmaxa超时码二分治类解法：deflargestRectangleArea(self,heights:List[int])->int:defsolve(l,r,d):如果l>=r:返回0如果l==r-1:返回heights[l]min_i=lmin_h=heights[l]fori,hinenumerate(heights[1+l:r]):如果h
