84. 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 heights = [2,1,5,6,2,3],

return 10.

解释参考点击打开链接

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