<p>Given an array of integers <code>heights</code> representing the histogram&#39;s bar height where the width of each bar is <code>1</code>, return <em>the area of the largest rectangle in the histogram</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg" style="width: 522px; height: 242px;" />
<pre>
<strong>Input:</strong> heights = [2,1,5,6,2,3]
<strong>Output:</strong> 10
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg" style="width: 202px; height: 362px;" />
<pre>
<strong>Input:</strong> heights = [2,4]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= heights.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= heights[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        '''
        Monotonic Stack
        T: O(n)
        S: O(n)
        stack = [[index, height]]
        If a int is less than both of its left and right neighobors,
        then the largest rectangle with width greater than 2 is no longer
        able to consider this int as its height, we can just pop it
        Likewise, whenever the height of the last int in the stack is
        greater than the cur int, we drop it and calculate the area from
        it till current, since the int cannot extend anymore when it encounter
        some smaller int after it
        '''
        res = 0
        stack = []
        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                res = max(res, height * (i - index))
                start = index
            
            stack.append([start, h])
        
        for i, h in stack:
            res = max(res, h * (len(heights) - i))

        return res
34300