Largest Rectangle in Histogram

Problem:
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.


Solution:
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = height.size();
        if (size == 0)
            return 0;
        int largest = 0;
        stack<pair<int, int> > height_index_stack;
       
        for (int i = 0; i < size; i++) {
            if (height_index_stack.empty() || height[i] > height_index_stack.top().first) {
                height_index_stack.push(make_pair(height[i], i));
            } else if (height[i] < height_index_stack.top().first) {
                int last_index;
                while (!height_index_stack.empty() &&
                        height_index_stack.top().first > height[i]) {
                    pair<int, int> last_poped = height_index_stack.top();
                    height_index_stack.pop();
                    last_index = last_poped.second;
                    int area = last_poped.first * (i - last_index);
                    largest = max(area, largest);
                }
                height_index_stack.push(make_pair(height[i], last_index));
            }
        }
       
        while (!height_index_stack.empty()) {
            pair<int, int> last_poped = height_index_stack.top();
            height_index_stack.pop();
            int last_index = last_poped.second;
            int area = last_poped.first * (size - last_index);
            largest = max(area, largest);
        }
        return largest;
    }
};


======== Awesome one by Leetcode forum ===========
class Solution {
public:
    int largestRectangleArea(vector<int> &h) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        stack<int> p;
    int i = 0, m = 0;
    h.push_back(0);
    while(i < h.size()) {
        if(p.empty() || h[p.top()] <= h[i])
            p.push(i++);
        else {
            int t = p.top();
            p.pop();
            m = max(m, h[t] * (p.empty() ? i : i - p.top() - 1 ));
        }
    }
    return m;
    }
};