Day 82, #84, Largest Rectangle in Histogram

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.

----------------------------------------------------------
for each single bar, calculate the largest rectangle that has the same height as the bar,
OJ Time Limit Exceeded

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int largest = 0;
        
        for (int i = 0; i < height.size(); i++) {
            int left = i - 1, right = i + 1;
            int length = 1;
            while (left >= 0 && height[left] >= height[i]) {
                length++;
                left--;
            }
            
            while (right < height.size() && height[right] >= height[i]) {
                length++;
                right++;
            }
            
            largest = max(largest,length * height[i]);
        }
        
        return largest;
    }
};

Solution #2
网上讲解很多，请google
要点
#1 原数组末尾插入0是为了清空并计算stack内所剩的数
#2 第18行: (topBar - st.top() - 1) + (i - topBar) = i - st.top() -  1
- topBar左边：因为从st.top（）到topBar之间的长方形都高于topBar，当计算以topBar为高度的面积时得包含之前的长方形
- topBar右边：到当前的i为止，所有的长方形都大于或等于topBar
#3 当stack为空时，说明之前所有经历过的长方形都高于topBar. 因为在某一个index时，stack里面比当前小的永远不会被pop出去
#4 stack所存的是index
#5 stack里的高度永远为递增
例子：{4,2,0,3,2,5}
情况1：

情况2：

情况3：

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> st;
        int largest = 0;
        height.push_back(0);
        
        for (int i = 0; i < height.size(); i++) {
            
            if (st.empty() || height[i] >= height[st.top()]) {
                st.push(i);
            }else {
                int topBar = st.top();
                st.pop();
                if (st.empty()) {
                    largest = max(largest,height[topBar] * i);
                }else {
                    largest = max(largest,height[topBar] * (i - st.top() - 1));
                }
                
                i--;
            }
        }

        return largest;
    }
};