[已解决]求最大矩形面积

Unicorn#

凑热闹

1. def MaxRectangle(heights)->int:
   
2.     f = lambda x:len(x)*min(x)
   
3.     n = len(heights)
   
4.     return max(f(heights[i:j])for i in range(n)for j in range(i+1, n+1))

复制代码

阴阳神万物主

Unicorn# 发表于 2019-11-20 21:49
凑热闹

跟这儿一样儿样儿的，超时呢

Stubborn

阴阳神万物主 发表于 2019-11-20 22:05
跟这儿一样儿样儿的，超时呢

一看就超时，哈哈

__mrsq__

1. class Solution:
   
2.     def largestRectangleArea(self, heights: List[int]) -> int:
   
3.         res=0
   
4.         numdict = []
   
5.         for i in heights:
   
6.             if numdict==[]:
   
7.                 numdict.append(i)
   
8.             elif i >= numdict[-1]:
   
9.                 numdict.append(i)
   
10.             else:
    
11.                 t = 0
    
12.                 for l in range(len(numdict)-1,-1,-1):
    
13.                     if numdict[l]>i:
    
14.                         t=t+1
    
15.                         res=max(res,numdict[l]*t)
    
16.                     else:
    
17.                         break
    
18.                 numdict = numdict[:-t]+(t+1)*[i]
    
19.         for i in set(numdict):
    
20.             res =max(res,i*(len(numdict)-numdict.index(i)))
    
21.         return res

复制代码

写了一个通过边缘的.....