柱状图中最大的矩形（宽任意）

1、宽都为1

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入: [2,1,5,6,2,3] 输出: 10 参考的链接： https://www.jianshu.com/p/6f48a96b8d5a

class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) heights = heights+[0] stack = [-1] max_area = 0 for i in range(n+1): while heights[i]<heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h*w) stack.append(i) return max_area

2、宽不唯一

自己的理解，可能有误， 菜鸟一枚，勿喷

def get_w( index,wide ): if index == 0: return wide[ 0 ] res = 0 for i in range(1, index ): res += wide[ i ] return res def largestRectangleArea(heights,wide): n = len(heights) heights = heights + [0] wide = wide + [0] stack = [-1] max_area = 0 for i in range(n + 1): while heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = get_w( i,wide ) - get_w( stack[-1],wide ) - 1 max_area = max(max_area, h * w) stack.append(i) return max_area if __name__ == '__main__': # https://leetcode-cn.com/problems/largest-rectangle-in-histogram/ # [2,1,5,6,5,3] [1,1,2,2,1,1] string = input().split(']') h_array = list(map(int, string[0][1:].split(','))) w_array = list(map(int, string[1].strip()[1:].split(','))) print('输入数据：', h_array, w_array) print('最大的面积：',largestRectangleArea(h_array, w_array))