Seawolf 发表于 2020-8-6 04:29:18

Leetcode 84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.




Above is a histogram where width of each bar is 1, given height = .




The largest rectangle is shown in the shaded area, which has area = 10 unit.



Example:

Input:
Output: 10

class Solution:
    def largestRectangleArea(self, heights: List) -> int:
      if heights == None or len(heights) == 0:
            return 0
      res = 0
      stack = []
      for i in range(len(heights) + 1):
            if i == len(heights):
                curt = -1
            else:
                curt = heights
            while stack and curt <= heights]:
                h = heights
                if len(stack) != 0:
                  w = i - stack[-1] - 1
                else:
                  w = i
                res = max(res, w * h)
            stack.append(i)
      return res
页: [1]
查看完整版本: Leetcode 84. Largest Rectangle in Histogram