84.Largest Rectangle in Histogram

Tags: Hard Stack

Link: https://leetcode.com/problems/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.

---

Example:

Input: [2,1,5,6,2,3]
Output: 10

---

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        heights.push_back(-1); //这样栈里面的所有元素都会弹出

        stack<int> s;
        int res = 0;
        int n = heights.size();
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && heights[s.top()] > heights[i]) {
                int cur = s.top(); s.pop();
                res = max(res, heights[cur] * (s.empty() ? i : i - s.top() - 1));
            }
            s.push(i);
        }

        return res;
    }
};

解析：

单调栈的方法，考虑每个矩形，它可以往右延申的条件就是下一个临近的矩形的高度不小于它本身的高度，如果小于了，那么就需要去除矩形本身，始终维护一个高度递增的序列。

那么特殊情况，如果临近的两个矩形高度相等怎么办，比如2，4，4，3的情况，其实最右边的4往左延申等价于第一个4往右边延申，所以不会产生遗漏。

另外的技巧就是在序列末尾添加一个-1，保证最后所有的情况都会被检测到。

去检验算法的时候可以有几个很典型的测试用例：

1 2 3 4 5
3 0 3 2 5
2 1 2

POJ 2559 同题。