<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:
    '''
    the factor that is going to limit us in terms of area is going to be the fact that we are going to be bounded by 
    the smallest recrangle in our array
    
    either get rid of that rectangle or we keep it 
    if we keep it then we will bound the rest of the rectangles to that height until we encounter a smaller rectangle then it will be bounded by that 
    '''
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack=[]
        maxarea = 0
        for i,h in enumerate(heights):
            startindex=i
            while stack and stack[-1][1]>h:
                index,height=stack.pop()
                maxarea=max(maxarea,height*(i-index))
                startindex=index
            stack.append((startindex,h))
        for i, h in stack:
            maxarea=max(maxarea,h*(len(heights)-i))
        return maxarea
        

        
32700