柱状图中最大的矩形 两种解法 （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)):
        	# 只有当前i对应的值 明确小于栈顶时才能出栈计算面积 因为相等时还不知道右边界在哪里
            while heights[stack[-1]] > heights[i]:
                hIndex = stack.pop()
                maxArea = max(maxArea, (i - stack[-1] - 1) * heights[hIndex])
            stack.append(i)
        return maxArea