package com.fishercoder.solutions;

import java.util.Stack;

/**
 * 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.

 For example,
 Given heights = [2,1,5,6,2,3],
 return 10.
 */
public class _84 {

    /**credit: https://leetcode.com/articles/largest-rectangle-histogram/#approach-5-using-stack-accepted
     * and https://discuss.leetcode.com/topic/7599/o-n-stack-based-java-solution*/
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        Stack<Integer> s = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i <= len; i++) {
            int h = (i == len ? 0 : heights[i]);
            if (s.isEmpty() || h >= heights[s.peek()]) {
                s.push(i);
            } else {
                int tp = s.pop();
                maxArea = Math.max(maxArea, heights[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }

}

@@ -514,13 +514,56 @@
 %0A%0A  
-  /**
+public static class Solution1 %7B%0A%0A    /**%0A     * 
 cred
@@ -737,16 +737,22 @@
 solution
+%0A     
 */%0A    p
@@ -801,26 +801,24 @@
 ts) %7B%0A      
-  
 int len = he
@@ -831,18 +831,16 @@
 length;%0A
-  
       St
@@ -873,26 +873,24 @@
 %3C%3E();%0A      
-  
 int maxArea 
@@ -894,18 +894,16 @@
 ea = 0;%0A
-  
       fo
@@ -937,28 +937,24 @@
 ) %7B%0A        
-   
- 
 int h = (i =
@@ -978,20 +978,16 @@
 ts%5Bi%5D);%0A
-    
         
@@ -1041,22 +1041,16 @@
         
- 
-     
 s.push(i
@@ -1060,20 +1060,16 @@
         
-  
-  
 %7D else %7B
@@ -1079,22 +1079,16 @@
         
-    
-  
 int tp =
@@ -1097,22 +1097,16 @@
 .pop();%0A
-      
         
@@ -1198,22 +1198,16 @@
         
-      
 i--;%0A   
@@ -1215,24 +1215,18 @@
     
-   
- 
 %7D%0A
-  
       %7D%0A
     
@@ -1217,26 +1217,24 @@
   %7D%0A      %7D%0A
-  
       return
@@ -1248,12 +1248,16 @@
 a;%0A    %7D
+%0A  %7D
 %0A%0A%7D%0A

refactor 84