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

 

문제 풀이:

지난번에 풀었던 문제와 알고리즘이 동일하다. 또 못푼건 함정 ㅎㅎ....

eazymean.tistory.com/130

[leetcode 85] Maximal Rectangle

 

class Solution {
    public int largestRectangleArea(int[] heights) {
        
        Stack<Integer> stk = new Stack<Integer>();
        int result = 0;
        int i=0;
        while(i<heights.length){
            if(stk.isEmpty() || heights[stk.peek()] <= heights[i]){
                stk.push(i);
                i++;
            }else {
                int top = stk.pop();
                int area = heights[top] * (stk.isEmpty()? i: (i-stk.peek()-1));
                result = Math.max(result, area);
            }
        }
        
        while(!stk.empty()){
            int top = stk.pop();
            int area = heights[top] * (stk.isEmpty()? i: (i-stk.peek()-1));
            result = Math.max(result, area);
            
        }
        
        return result;
    }
}