LeetCode: Largest Rectangle in Histogram

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.

---

The idea is to compute the area of each rectangle of height at each index. And we can use a stack to help find the left bound and right bound of each column. If the current column is higher than the top of the stack. Push it into the stack since it cannot be the right bound of the top of the stack whereas the top of the stack will be its left bound.

C++ Code:

/*
 * func: largest_rectangle_area
 * goal: find the area of largest rectangle in the histogram
 * @param height: vector of heights
 * return: the largest rectange area
 */
/*
 * We use a stack to help find the left bound and right bound of each column
 * complexity: time O(n), space O(n)
 */
int largest_rectangle_area(vector<int> &height){
    int max_area = 0;
    stack<int> area_helper;
    height.emplace_back(0);
    int i = 0;
    
    while(i<height.size()){
        //If the stack is empty or current hist is height than the top of the stack
        if(area_helper.empty() || height[area_helper.top()] <= height[i]){
            area_helper.emplace(i++);
        }else{
            //If current hist is lower than the top of the stack, then we find the right bound
            //of the top hist in the stack, and the index below top of the stack will be the left bound of that hist
            int top_index = area_helper.top();
            area_helper.pop();
            max_area = max(max_area, height[top_index] * (area_helper.empty() ? i : i - area_helper.top() - 1));
        }
    }
    
    return max_area;
}

Python Code:

# func: find the largest rectangle area in the histogram
# @param height: a list of heights
# @return: the largest area
# complexity: time O(n), space O(n)
def largest_rectangle_area(height):
    max_area = 0
    stack = []
    height.append(0)
    index = 0
    while index < len(height):
        if not stack or height[index] >= height[stack[-1]]:
            stack.append(index)
            index += 1
        else:
            top_index = stack[-1]
            stack.pop(-1)
            if not stack:
                current_area = height[top_index] * index
            else:
                current_area = height[top_index] * (index - stack[-1] - 1)

            max_area = max(max_area, current_area)

    return max_area