LargestRectangleInHistogram { public static int largestRectangleArea(int[] heights) { if (heights.length == 0) return 0; Stack<Integer> stack = new Stack<>(); int index = 0; int maxArea = 0; while (index < heights.length) { if (stack.isEmpty() || heights[index] > heights[stack.peek()]) { stack.push(index++); } else { int top = stack.pop(); maxArea = Math.max(maxArea, heights[top] * (stack.isEmpty() ? index : index - stack.peek() - 1)); } } while (!stack.isEmpty()) { int top = stack.pop(); maxArea = Math.max(maxArea, heights[top] * (stack.isEmpty() ? index : index - stack.peek() - 1)); } return maxArea; }  static int largestRectangleArea(int[] heights);  }
@Test(dataProvider = "histogramData") public void test(int[] histogram, int expected) { assertEquals(LargestRectangleInHistogram.largestRectangleArea(histogram), expected); }