84. Largest Rectangle in Histogram

Link

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

Solution

這題用stack的方式去找出所有可能矩形的right, left邊界。

作法很tricky。

巡迴arrays中的所有元素，依序擺入stack中，並確保裡面是升序的元素值。當巡迴到不是升序的元素，無法擺入stack就以stack.peek()所指的位置(ex. index) 的元素為高開始進行找right , left的動作，

已知 heights[index] > heights[left]，

height[index] > height[right]

left <= index <= right

寬就是 right - left - 1

public int find(int heights[]){

    if(heights == null || heights.length == 0) return 0;
    Stack<Integer> s = new Stack<>();
    for(int i = 0; i <= heights.length; i++){
        int value = (i == heights.length) ? 0 : heights[i];
        if(s.isEmpty() || heights[s.peek()] <= value){
            s.push(i);
        }
        else{
            int height = heights[s.pop()];
            int right = i;
            int left = s.isEmpty() ? -1 : s.peek();
            maxValue = Math.max(maxValue, height * (right - left - 1));
            i--;
        }
    }
    return maxValue;

}