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

柱状图中最大的矩形 两种解法 （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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。