LeetCode 0084 - Largest Rectangle in Histogram

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<pair<int, int>> s;
        int res = 0;
        for (int i = 0; i < heights.size(); i++) {
            if (s.empty() || s.top().first < heights[i])
                s.push(make_pair(heights[i], 1));
            else {
                int pre_weight = 0;
                while (s.size() && s.top().first >= heights[i]) {
                    pair<int, int> cur = s.top();
                    s.pop();
                    res = max(res, cur.first * cur.second);
                    if (s.size() && s.top().first >= heights[i])
                        s.top().second += cur.second;
                    pre_weight = cur.second;
                }
                s.push(make_pair(heights[i], 1 + pre_weight));
            }
        }
        while (s.size()) {
            pair<int, int> cur = s.top();
            s.pop();
            if (s.size())
                s.top().second += cur.second;
            res = max(res, cur.first * cur.second);
        }
        return res;
    }
};