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.

The trick is to maintain a stack, for each element, if stack is empty, or this element is bigger than top of the stack, then push this element in the top of stack; else find rectangle in stack. For example, we want find the largest rectangle from the above histogram, let’s simulate how this algorithm works when i = 0 : 6

i = 0: height[0] is 2, and now stack is empty, so push(0), i ++;

i = 1: height[1] is 1, which is less than top of stack height[0], so we find a rectangle which forms by height[0], and area is 2;

i = 1: height[1] is 1, stack is empty, push(1), i++;

i = 2: height[2] is 5, which is bigger than top of stack, so push(2), i++;

i = 3: height[3] is 6, which is bigger than top of stack, so push(3), i++;

i = 4: height[4] is 2, which is less than stack top, we find a rectangle which forms by height[3], area is 6;

i = 4: height[4] is 2, which is less than stack top, we find a rectangle which forms by height[2] and height[3], which area is 5 * 2 = 10;

i = 4: height[4] is 2, bigger than top of stack, push(4), i++;

i = 5: height[5] is 3, bigger, push(5), i++;

i = 6: height[6] is 0, less than stack top (now we have 1, 4, 5 in stack, and height[1], height[4], height[5] are 1, 2, 3), 0 is less than any of the three elements in stack, so we find rectangles that area is 3 * 1 = 3, 2 * 2 = 4, 1 * 5 = 5.

The largest rectangle we found above have area of 10, so return 10.

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

🙂

## One Comment

College – SparkNotes