84. Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

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

Thoughts

http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html

给不同高度的histogram，问能形成的最大长方形面积。暴力法是对i，遍历其前面直到比它矮的，这段长度再乘以i的高即以i为底能形成的面积最大长方形；同理再遍历其后面，最后两段面积相加。也就是说想知道i前面有多少连续比它高的，而且这段元素在给i之后的作左边元素时高度都受限于h[i]。维护以高度为评判的递增序列，用stack，里头存index，当遇到高度比栈顶小的height[i]就弹出，计算它的index与i的距离 (宽, 因为这些元素都是比当前栈顶高的, 能以栈顶的高度形成面积), 再乘以它的高度即这个块能形成的最大面积。

Code

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        s, res = [], 0
        heights.append(0)
        for i, h in enumerate(heights):
            while len(s) > 0 and h < heights[s[-1]]:
                hei = heights[s[-1]]
                s.pop()
                wid = i - s[-1] - 1 if len(s) > 0 else i
                res = max(res, hei * wid)
            s.append(i)
        return res

/*
 * @lc app=leetcode id=84 lang=cpp
 *
 * [84] Largest Rectangle in Histogram
 */
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> ind;
        heights.push_back(0);
        int res = 0;
        for (int i = 0; i < heights.size(); ++i) {
            while (!ind.empty() && heights[ind.top()] > heights[i]) {
                const int h = heights[ind.top()];
                ind.pop();
                const int w = ind.empty() ? i : i - ind.top() - 1;
                res = max(res, h * w); 
            }
            ind.push(i);
        }
        return res;
    }
};

Analysis

时空复杂度O(n). 注意heights最后一个要是0, 确保能正确弹出所有元素. 还有int w = stack.isEmpty() ? i : (i - stack.peek() - 1)