BinarySearch 0560 Area Under Histogram

Problem statement

https://binarysearch.com/problems/Area-Under-Histogram/

Solution

Equal to Leetcode 0084. Largest Rectangle in Histogram

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, heights):
        stack, ans = [], 0
        for i, h in enumerate(heights + [0]):
            while stack and heights[stack[-1]] >= h:
                H = heights[stack.pop()]
                W = i if not stack else i-stack[-1]-1
                ans = max(ans, H*W)
            stack.append(i)
        return ans