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 {

  public static class Solution1 {

    /**
     * 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;
    }
  }

}

@@ -58,440 +58,8 @@
 k;%0A%0A
-/**%0A * 84. Largest Rectangle in Histogram%0A *%0A * Given n non-negative integers representing the histogram's bar height where%0A * the width of each bar is 1, find the area of largest rectangle in the histogram.%0A%0A Above is a histogram where width of each bar is 1, given height = %5B2,1,5,6,2,3%5D.%0A The largest rectangle is shown in the shaded area, which has area = 10 unit.%0A%0A For example,%0A Given heights = %5B2,1,5,6,2,3%5D,%0A return 10.%0A */%0A
 publ
@@ -74,16 +74,18 @@
  _84 %7B%0A%0A
+  
   public
@@ -119,12 +119,20 @@
     
-/**%0A
+    /**%0A    
     
@@ -238,16 +238,20 @@
 ed%0A     
+  
+  
 * and ht
@@ -327,15 +327,23 @@
     
-*/%0A
+    */%0A   
     
+ 
 publ
@@ -383,24 +383,30 @@
  heights) %7B%0A
+      
       int le
@@ -431,16 +431,22 @@
 ;%0A      
+  
+    
 Stack%3CIn
@@ -473,24 +473,30 @@
 %3C%3E();%0A      
+     
+ 
 int maxArea 
@@ -500,16 +500,22 @@
 ea = 0;%0A
+      
       fo
@@ -549,24 +549,32 @@
 ) %7B%0A        
+  
+      
 int h = (i =
@@ -606,16 +606,24 @@
         
+   
+     
 if (s.is
@@ -669,16 +669,26 @@
         
+   
+       
 s.push(i
@@ -698,16 +698,24 @@
         
+  
+      
 %7D else %7B
@@ -721,24 +721,34 @@
 %7B%0A          
+   
+       
 int tp = s.p
@@ -749,24 +749,34 @@
  = s.pop();%0A
+          
           ma
@@ -868,13 +868,31 @@
     
+ 
+         
 i--;%0A
+        
     
@@ -899,26 +899,38 @@
     %7D%0A      
+ 
-%7D%0A
+     %7D%0A      
       return
@@ -943,17 +943,23 @@
 ea;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%0A%7D%0A

refactor 84