add 84

fishercoder1534 · fishercoder1534 · commit 742287de1d87 · 2017-06-17T09:28:23.000-07:00
diff --git a/README.md b/README.md
@@ -443,6 +443,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |87|[Scramble String](https://leetcode.com/problems/scramble-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_87.java)|O(?) |O(?)|Hard| Recursion
 |86|[Partition List](https://leetcode.com/problems/partition-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/PartitionList.java)|O(?) |O(?)|Medium|
 |85|[Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)|[Solution](../master/src/main/java/com/fishercoder/solutions/MaximalRectangle.java)|O(m*n) |O(n)|Hard|DP
+|84|[Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_84.java)|O(n) |O(n)|Hard|Array, Stack
 |83|[Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_83.java)|O(n) |O(1)|Medium| Linked List
 |82|[Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_82.java)|O(n) |O(1)|Medium| Linked List
 |81|[Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/SearchinRotatedSortedArrayII.java)|O(logn)|O(1)|Medium|Binary Search
diff --git a/src/main/java/com/fishercoder/solutions/_84.java b/src/main/java/com/fishercoder/solutions/_84.java
@@ -0,0 +1,41 @@
+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;
+    }
+
+}
