今天的题目如下所示：
题目
这道题，第一眼看过去，我想到的解法就是遍历每一个数，然后从这个数往两边搜寻连续的比这个数大的数字的个数，用个数乘以这个数的大小，就得到了这个数可以得到的最大数字。原理如下图所示：
示例
这种方法的代码如下所示，分了头尾中间三种情况进行讨论处理：
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
lens = len(heights)
if lens == 1:
return heights[0]
if lens == 0:
return 0
max_area = 0
for i in range(lens):
area = self.SearchHigher(heights, i, lens-1)
if area > max_area:
max_area = area
return max_area
def SearchHigher(self, lists, loc, limit):
width = 1
if loc == 0:
loc1 = loc
while lists[loc1+1] >= lists[loc]:
width += 1
loc1 += 1
if loc1 == limit:
break
return lists[loc]*width
elif loc == limit:
loc1 = loc
while lists[loc1-1] >= lists[loc]:
width += 1
loc1 -= 1
if loc1 == 0:
break
return lists[loc]*width
else:
loc1 = loc
while lists[loc1+1] >= lists[loc]:
width += 1
loc1 += 1
if loc1 == limit:
break
loc2 = loc
while lists[loc2-1] >= lists[loc]:
width += 1
loc2 -= 1
if loc2 == 0:
break
return lists[loc]*width
从原理上来看，这种方法是没有问题的，但是实际上呢，这种方法因为对于数组内的每一个元素都需要往两边逐个进行搜寻，因此效率很低。在leetcode上跑超时了。于是我决定放在spyder上看看跑完一遍要多久，结果很令人绝望……
跑完一轮的时间超过了30秒
这个方法不行，于是我决定去评论区看看有没有什么思路。第一个思路就是一个很好的方法，于是我决定按照这种方法来写：传送门
评论区顶端的评论
依葫芦画瓢，我按照这个思路写的代码如下所示：
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0)
lens = len(heights)
max_area = 0
cache_length = 0
loc = 0
for i in range(lens-1):
if heights[i] <= heights[i+1]:
pass
else:
width = 0
while heights[i] > heights[i+1]:
width += 1
area = heights[i] * width
if max_area < area:
max_area = area
heights[i] = heights[i+1]
i -= 1
if i < 0:
break
return max_area
最后的结果也很令人满意，🐂！
一个满意的结果
