Interview-Questions/84 Largest Rectangle in Histogram at master · shashanksriva/Interview-Questions · GitHub

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
51
52
53
54
55
56
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].


 public int largestRectangleArea(int[] heights) {


    int[] left = new int[heights.length];
    int[] right = new int[heights.length];
    int[] width = new int[heights.length];
    Stack<Integer> stack = new Stack();


       //width --- left
        for(int i=0;i<heights.length;i++){

            while(!stack.isEmpty() && heights[i]<=heights[stack.peek()]){
                stack.pop();
            }

            if(stack.isEmpty()){
                left[i] = -1;
            }else{
                left[i] = stack.peek();
            }

            stack.add(i);
        }
        stack.clear();
        //width --- right
        for(int i=heights.length-1;i>=0;i--){

            while(!stack.isEmpty() && heights[i]<=heights[stack.peek()]){
                stack.pop();
            }

            if(stack.isEmpty()){
                right[i] = heights.length;
            }else{
                right[i] = stack.peek();
            }

            stack.add(i);
        }

        int area = 0;

         for(int i=0;i<heights.length;i++){
            width[i] = right[i]-left[i]-1;
            area = Math.max(heights[i]* width[i] ,area);
         }

        return area;
    }