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.
image.png
Stack Solution
- 对每个数来说，到array中下一个比它小的数位置的长度就是rectangle的width，所以在stack中放入array的index，然后当stack顶的数比它大时，计算rectangle面积
- 如果最后一段是递增的话，就会没有得到处理，所以在最后加上0来处理最后一段数据
- Time complexity: O(n)
class Solution {
public int largestRectangleArea(int[] heights) {
int maxVal = 0;
Stack<Integer> stack = new Stack<Integer>();
for (int i=0; i<=heights.length; i++) {
int h = i == heights.length ? 0 : heights[i];
while (! stack.isEmpty() && heights[stack.peek()] > h) {
int height = heights[stack.pop()];
int start = stack.isEmpty() ? -1 : stack.peek();
maxVal = Math.max(maxVal, height * (i - start - 1));
}
stack.push(i);
}
return maxVal;
}
}
Divide and conquer Solution
- 找array中的min，对min左和min右（都不包含min）去recursively找min，然后把min和#bar相乘得到area
- 用linear找min/quick sort worst case的time complexity都会达到和brute force一样的O(n^2)，所以要用segment tree来完成
- Time complexity: O(nlog(n))
Reference GeeksForGeeks Largest Rectangular Area in a Histogram | Set 1
