package leetcode;

import java.util.Stack;

/**
 * https://leetcode.com/problems/largest-rectangle-in-histogram/
 */
public class Problem84 {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int idx = 0;
        int maxArea = 0;
        while (idx < height.length) {
            if (stack.isEmpty() || height[stack.peek()] <= height[idx]) {
                stack.push(idx);
                idx++;
            } else {
                int topIdx = stack.pop();
                int peekIdx = (stack.isEmpty()) ? -1 : stack.peek();
                int width = idx - peekIdx - 1;
                int area = height[topIdx] * width;
                if (maxArea < area) {
                    maxArea = area;
                }
            }
        }
        while (!stack.isEmpty()) {
            int topIdx = stack.pop();
            int peekIdx = (stack.isEmpty()) ? -1 : stack.peek();
            int width = idx - peekIdx - 1;
            int area = height[topIdx] * width;
            if (maxArea < area) {
                maxArea = area;
            }
        }
        return maxArea;
    }
}

@@ -199,110 +199,195 @@
     
-Stack%3CInteger%3E stack = new Stack%3C%3E();%0A        int idx = 0;%0A        int maxArea = 0;%0A        while (idx
+if (height.length == 0) %7B%0A            return 0;%0A        %7D%0A        Stack%3CIndexValue%3E leftStack = new Stack%3C%3E();%0A        int%5B%5D leftCounts = new int%5Bheight.length%5D;%0A        for (int i = 0; i
  %3C h
@@ -398,16 +398,21 @@
 t.length
+; i++
 ) %7B%0A    
@@ -423,13 +423,21 @@
     
-if (s
+while (!leftS
 tack
@@ -451,18 +451,18 @@
 y() 
-%7C%7C
+&&
  height%5B
 stac
@@ -461,36 +461,36 @@
 ght%5B
-stack.peek()%5D %3C= height%5Bidx%5D
+i%5D %3C= leftStack.peek().value
 ) %7B%0A
@@ -509,22 +509,22 @@
     
-s
+leftS
 tack.p
-ush(idx
+op(
 );%0A 
@@ -538,18 +538,9 @@
     
-    idx++;
+%7D
 %0A   
@@ -552,126 +552,154 @@
     
-%7D else %7B%0A                int topIdx = stack.pop();%0A                int peekIdx = (stack.isEmpty()) ? -1 : stack.peek()
+if (!leftStack.isEmpty()) %7B%0A                leftCounts%5Bi%5D = i - leftStack.peek().index;%0A            %7D else %7B%0A                leftCounts%5Bi%5D = i + 1
 ;%0A  
@@ -712,41 +712,66 @@
     
+%7D%0A
     
-int width = idx - peekIdx - 1
+        leftStack.push(new IndexValue(i, height%5Bi%5D))
 ;%0A  
@@ -772,32 +772,35 @@
 ));%0A        
+%7D%0A%0A
         
 int area = h
@@ -791,134 +791,290 @@
     
-int area = height%5BtopIdx%5D * width;%0A                if (maxArea %3C area) %7B%0A                    maxArea = area;%0A                %7D
+Stack%3CIndexValue%3E rightStack = new Stack%3C%3E();%0A        int%5B%5D rightCounts = new int%5Bheight.length%5D;%0A        for (int i = height.length - 1, j = 0; i %3E= 0; i--, j++) %7B%0A            while (!rightStack.isEmpty() && height%5Bi%5D %3C= rightStack.peek().value) %7B%0A                rightStack.pop();
 %0A   
@@ -1096,27 +1096,23 @@
     
-%7D%0A        while (!s
+    if (!rightS
 tack
@@ -1141,96 +1141,189 @@
     
-int topIdx = stack.pop();%0A            int peekIdx = (stack.isEmpty()) ? -1 : stack.peek(
+    rightCounts%5Bi%5D = rightStack.peek().index - i;%0A            %7D else %7B%0A                rightCounts%5Bi%5D = j + 1;%0A            %7D%0A            rightStack.push(new IndexValue(i, height%5Bi%5D)
 );%0A 
@@ -1332,89 +1332,188 @@
     
+ %7D%0A
      
+   
 int 
-width = idx - peekIdx - 1;%0A            int area = height%5BtopIdx%5D * width
+answer = Integer.MIN_VALUE;%0A        for (int i = 0; i %3C height.length; i++) %7B%0A            answer = Math.max(answer, height%5Bi%5D * (rightCounts%5Bi%5D + leftCounts%5Bi%5D - 1))
 ;%0A  
@@ -1522,74 +1522,153 @@
     
+%7D%0A
     
-if (maxArea %3C area) %7B%0A                maxArea = area
+    return answer;%0A    %7D%0A%0A    private static class IndexValue %7B%0A        private final int index;%0A        private final int value
 ;%0A
+%0A
         
     
@@ -1667,47 +1667,123 @@
     
-    %7D%0A        %7D%0A        return maxArea;
+public IndexValue(int index, int value) %7B%0A            this.index = index;%0A            this.value = value;%0A        %7D
 %0A   

Update problem 84