Largest Rectangle in Histogram

文章目录

1. 1. Largest Rectangle in Histogram
   1. 1.1. 题目
   2. 1.2. 思路
   3. 1.3. 解题

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.

思路

利用栈，当前元素比栈顶元素对应的值要大，则入栈（入栈的是当前元素的索引）。否则出栈，出栈元素为t，并计算面积。
maxArea = max(maxArea, height[t] * (stk.empty() ? i : i - stk.top() - 1));

解题

c++版

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        height.push_back(0);  
        stack<int> stk;  
        int i = 0;  
        int maxArea = 0;  
        while(i < height.size()){  
            if(stk.empty() || height[stk.top()] <= height[i]){  
                stk.push(i++);  
            }else {  
                int t = stk.top();  
                stk.pop();  
                maxArea = max(maxArea, height[t] * (stk.empty() ? i : i - stk.top() - 1));  
            }  
        }  
        return maxArea;  
    }
};

python版

class Solution:
    # @param {integer[]} height
    # @return {integer}
    def largestRectangleArea(self, height):
        height.append(0)
        s=[]
        i=0
        maxarea=0
        while i<len(height):
            if(len(s)==0 or height[i]>=height[s[-1]]):
                s.append(i)
                i=i+1
            else:
                tmp=s.pop()
                if(len(s)==0):
                    count=i
                else:
                    count=i-1-s[-1]
                maxarea=max(maxarea,height[tmp]*count)
        return maxarea