Given an array of integers heights
representing the histogram's bar height where the width of each bar is 1
, return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4]
Output: 4
Constraints:
-
1 <= heights.length <= 105
-
0 <= heights[i] <= 104
SOLUTION:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
next_lowest = [n for i in range(n)]
prev_lowest = [-1 for i in range(n)]
maxArea = 0
inc_stack = []
for i in range(n):
while len(inc_stack) > 0 and heights[i] < heights[inc_stack[-1]]:
curr = inc_stack.pop()
next_lowest[curr] = i
if len(inc_stack) > 0:
prev_lowest[i] = inc_stack[-1]
inc_stack.append(i)
for i in range(n):
currArea = (next_lowest[i] - prev_lowest[i] - 1) * heights[i]
maxArea = max(maxArea, currArea)
return maxArea
# class Solution:
# def largestRectangleArea(self, heights: List[int]) -> int:
# n = len(heights)
# maxArea = 0
# for i in range(n):
# curr = heights[i]
# left = i
# right = i
# while left >= 0 and heights[left] >= curr:
# left -= 1
# left += 1
# while right < n and heights[right] >= curr:
# right += 1
# right -= 1
# maxArea = max(maxArea, curr * (right - left + 1))
# return maxArea
# class Solution:
# def makeSeg(self, arr, i, j):
# if (i, j) in self.seg:
# return self.seg[(i, j)]
# if i == j:
# self.seg[(i, j)] = arr[i]
# return arr[i]
# mid = (i + j) // 2
# curr = min(self.makeSeg(arr, i, mid), self.makeSeg(arr, mid + 1, j))
# self.seg[(i, j)] = curr
# return curr
# def getMin(self, arr, i, j, ni, nj):
# if ni >= i and nj <= j:
# return self.seg[(ni, nj)]
# if (ni < i and nj < i) or (ni > j and nj > j):
# return float('inf')
# mid = (ni + nj) // 2
# return min(self.getMin(arr, i, j, ni, mid), self.getMin(arr, i, j, mid + 1, nj))
# def largestRectangleArea(self, heights: List[int]) -> int:
# self.seg = {}
# n = len(heights)
# if n == 1:
# return heights[0]
# self.makeSeg(heights, 0, n - 1)
# mrec = float('-inf')
# for i in range(n):
# for j in range(i, n):
# mrec = max(mrec, (j - i + 1) * self.getMin(heights, i, j, 0, n - 1))
# return mrec
# class Solution:
# def largestRectangleArea(self, heights: List[int]) -> int:
# n = len(heights)
# areas = []
# maxArea = float('-inf')
# areas.append((0, heights[0]))
# for i in range(1, n):
# if heights[i] < areas[-1][1]:
# maxArea = max(maxArea, (i - areas[-1][0]) * areas[-1][1])
# areas.pop()
# areas.append((i, heights[i]))
# return maxArea
Top comments (0)