柱状图中最大的矩形 两种解法 （Python）

​​LeetCode链接​​

暴力法1：两重循环遍历 时间复杂度 O(N^3)

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heightsLen = len(heights)
maxArea = 0
# 此处i需要遍历数组中的全部值
for i in range(heightsLen):
for j in range(i, heightsLen):
minHeight = math.inf
for k in range(i , j + 1):
minHeight = min(minHeight, heights[k])
maxArea = max(maxArea, (j - i + 1) * minHeight)
return maxArea

暴力法2：一重循环 时间复杂度 O(N^2)

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
heightsLen = len(heights)
for i in range(heightsLen):
left, right = i , i
curHeight = heights[i]
# 找出每一个矩形 左右的边界（高度>=当前矩形的高度）
while left > 0 and heights[left - 1] >= curHeight:
left -= 1
while right < heightsLen - 1 and heights[right + 1] >= curHeight:
right += 1
maxArea = max(maxArea, curHeight * (right - left + 1))
return maxArea

单调栈 时间复杂度 O(N)

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
# 初始栈中 加入一个 -1索引 解决 index为0的元素的面积计算边界问题
stack = [-1]
# 数组非负 最后添加一个元素0 可以将栈中所有的非0高度元素都计算面积
# 若数组中包含0 则最终结束时 栈内会剩下高度为0的下标 面积肯定为0 无需处理
heights.append(0)
for i in range(len(heights)):
while heights[stack[-1]] > heights[i]:
hIndex = stack.pop()
maxArea = max(maxArea, (i - stack[-1] - 1) * heights[hIndex])
stack.append(i)
return maxArea