class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> nearest_smaller_left(heights.size()); // indices
        auto nearest_smaller_right = nearest_smaller_left;

        stack<int> min_stack;
        for (int i = 0; i < heights.size(); ++i) {
            while(!min_stack.empty() && heights[min_stack.top()] >= heights[i])
                min_stack.pop();

            nearest_smaller_left[i] = min_stack.empty() ? -1 : min_stack.top();
            min_stack.push(i);
        }
        min_stack = {};
        for (int i = heights.size() - 1; i >= 0; --i) {
            while(!min_stack.empty() && heights[min_stack.top()] >= heights[i])
                min_stack.pop();

            nearest_smaller_right[i] = min_stack.empty() ? heights.size() : min_stack.top();
            min_stack.push(i);
        }

        int max_area = 0;
        for (int i = 0; i < heights.size(); ++i) {
            int width = nearest_smaller_right[i] - nearest_smaller_left[i] - 1;
            max_area = max(max_area, heights[i] * width);
        }

        return max_area;
    }
};