<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
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        // Intuition: Keep a monotonically increasing stack,
        // this means all heights on the stack will be less than the one in front of it
        // so this means, that when we encounter a height that is less than whatever is on top of the stack
        // now, we can extend the height on the back of the stack backwards until whatever the previous index before it on the stack was
        // so we get that height on the back and pop it from the stack,
        // then we grab the next index previous to that, but we keep it on the stack
        // but this size from whatever on the top of the stack to the previous before it will be the size of the rectangle
        // and the height of the rectangle will be whatever the height on top of the stack was
        stack<int> s;
        int res = 0;
        // temp array to avoid modifying the input array
        vector<int> h(heights);
        // handles the case where there are elements in the stack after finishing the iteration, 
        // so that we can consider these elements for the solution
        h.push_back(0);

        for (int i = 0; i < h.size(); i++)
        {
            // keep the stack monotonically increasing
            while (!s.empty() && h[s.top()] > h[i])
            {
                int curHeight = h[s.top()];
                s.pop();
                // handles edge case where current window 
                // covers the whole array so far to index i - 1 (because current height is top of stack)
                int left = -1;
                if (!s.empty())
                    left = s.top();

                // we do -1 because the current index i, is not included in this window
                int curWindowSize = i - left - 1;
                res = max(res, curHeight * curWindowSize);
            }
            // keep pushing because we need to consider each height
            s.push(i);
        }

        return res;
    }
};
86336