<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 {
private:
    struct Range {
        int begin;
        int end; // not included
        int tail;
    };
public:
    int largestRectangleArea(vector<int>& heights) {
        
        // The maximum area found so far.

        int maxArea = 0;

        // The total number of bars.

        int numBars = heights.size();

        // Stack to keep track of the indices of the bars.

        stack<int> indexStack;

        // Vector to store the index of the left nearest smaller bar for each bar.

        vector<int> leftNearest(numBars, -1);

        // Vector to store the index of the right nearest smaller bar for each bar.

        vector<int> rightNearest(numBars, numBars);


        for (int i = 0; i < numBars; ++i) {

            // Pop elements from the stack until the current bar is taller than the stack's top bar.

            while (!indexStack.empty() && heights[indexStack.top()] > heights[i]) {

                // Set the right nearest smaller bar for the popped bar.

                rightNearest[indexStack.top()] = i;

                indexStack.pop();

            }

            // If the stack is not empty, then the current top is the left nearest smaller bar.

            if (!indexStack.empty()) leftNearest[i] = indexStack.top();

            // Push current bar to stack.

            indexStack.push(i);

        }


        // Calculate the maximum area for each bar considering the nearest smaller bars to the left and right.

        for (int i = 0; i < numBars; ++i) {
            /*printf("i: %d, height: %d, leftPos: %d, rightPos: %d, square: %d \n", 
            i, heights[i], leftNearest[i], rightNearest[i], heights[i] * (rightNearest[i] - leftNearest[i] - 1));*/
            maxArea = max(maxArea, heights[i] * (rightNearest[i] - leftNearest[i] - 1));
        }


        // Return the maximum area found.

        return maxArea;
    }
};
85851