LeetCode [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.

Example:

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

class Solution { public: int largestRectangleArea(vector<int>& height) { stack<int> stk; int area = 0; height.push_back(0); int n = height.size(); for(int i=0; i<n; ++i){ while(!stk.empty() && height[i]<height[stk.top()]){ int h = height[stk.top()]; stk.pop(); int l = stk.empty()?-1:stk.top(); area = max(area, h*(i-l-1)); } stk.push(i); } return area; } }; class Solution { public: int largestRectangleArea(vector<int>& height) { int n = height.size(); vector<int> left(n), right(n); int area = 0; for(int i=0; i<n; ++i){ left[i] = i; int j = i-1; while(j>=0 && height[j]>=height[i]){ j = left[j]-1; } left[i] = j+1; } for(int i=n-1; i>=0; --i){ right[i] = i; int j = i+1; while(j<n && height[j]>=height[i]){ j = right[j]+1; } right[i] = j-1; area = max(area, height[i]*(right[i]-left[i]+1)); } return area; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

//Java class Solution { public int largestRectangleArea(int[] heights) { Stack<Integer> stk = new Stack<>(); int area = 0; int[] newHeights = new int[heights.length+1]; System.arraycopy(heights, 0, newHeights, 0, heights.length); newHeights[newHeights.length-1] = 0; for(int i=0; i<newHeights.length; ++i) { while(!stk.empty() && newHeights[i] < newHeights[stk.peek()]) { int h = newHeights[stk.pop()]; int l = stk.empty() ? -1 : stk.peek(); area = Math.max(area, h * (i-l-1)); // System.out.println(l + " " + i + " " + h + " " + area); } stk.push(i); } return area; } }