084.md

84. Largest Rectangle in Histogram

Solution 1 (O(n))

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        # First point smaller than current point on the right side
        stack, r_index = [], [len(heights)] * len(heights)
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                r_index[stack.pop()] = i
            stack.append(i)
        # First point smaller than current point on the left side
        stack, l_index = [], [-1] * len(heights)
        for i in range(len(heights) - 1, -1, -1):
            while stack and heights[i] < heights[stack[-1]]:
                l_index[stack.pop()] = i
            stack.append(i)
        ans = 0
        for i in range(len(heights)):
            ans = max(ans, heights[i] * (r_index[i] - l_index[i] - 1))
        return ans

Solution 2 (O(n))

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights.append(0)
        stack = [-1]
        ans = 0
        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(ans, h * w)
            stack.append(i)
        return ans