# 84. Largest Rectangle in Histogram

Givennnon-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.

![](https://leetcode.com/static/images/problemset/histogram.png)

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

![](https://leetcode.com/static/images/problemset/histogram_area.png)

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

For example,\
Given heights =`[2,1,5,6,2,3]`,\
return`10`.

**Thoughts:**

1. have a stack to record increasing index
2. while current index is less that the top of the stack, update the maximum area
3. having a increasing stack is because as index gets larger, the **only** possible way for rectangle starting from larger index is due to its larger height value.

**Code time complexity: O(n), space complexity: O(n)**

```cpp
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        s.push(-1);
        int ans = 0;
        int n = heights.size();
        for(int i = 0; i < n; i++){
            while((s.top()!= -1) && heights[s.top()] >= heights[i]){
                int last_idx = s.top(); s.pop();
                ans = max(ans, heights[last_idx] * (i - s.top() - 1));
            }
            s.push(i);
        }
        // reach the end of list
        while(s.top()!= -1){
            int last_idx = s.top(); s.pop();
            ans = max(ans, (heights[last_idx]) * (n - 1 - s.top()));
        }

        return ans;
    }
};
```

**Code using 0 padding at the end and vector as stack**

```cpp
 class Solution {
    public:
        int largestRectangleArea(vector<int> &height) {

            int ret = 0;
            height.push_back(0);
            vector<int> index;

            for(int i = 0; i < height.size(); i++)
            {
                while(index.size() > 0 && height[index.back()] >= height[i])
                {
                    int h = height[index.back()];
                    index.pop_back();

                    int sidx = index.size() > 0 ? index.back() : -1;
                    if(h * (i-sidx-1) > ret)
                        ret = h * (i-sidx-1);
                }
                index.push_back(i);
            }

            return ret;
        }
    };
```

Special thanks to [sipiprotoss5](https://discuss.leetcode.com/user/sipiprotoss5)'s for the last [solution](https://discuss.leetcode.com/topic/3913/my-concise-c-solution-ac-90-ms)