# One problem in No.84: largest rectangle in histogram

• The current algorithm that using stack to solve this problem seems lacking some test cases. The code below is the one passed OJ, but I do think there is a test case that this code cannot pass.

The test case is [3,1,3,4,2,3], it is easily to see the max area is 8, which cover the last 4 histograms with height 2, but I do not think the algorithm will return the correct answer.

Here is the code in java:
public class Solution {

// O(n) using one stack
public int largestRectangleArea(int[] height) {
// Start typing your Java solution below
// DO NOT write main() function
int area = 0;
java.util.Stack<Integer> stack = new java.util.Stack<Integer>();
for (int i = 0; i < height.length; i++) {
if (stack.empty() || height[stack.peek()] < height[i]) {
stack.push(i);
} else {
int start = stack.pop();
int width = stack.empty() ? i : i - stack.peek() - 1;
area = Math.max(area, height[start] * width);
i--;
}
}
while (!stack.empty()) {
int start = stack.pop();
int width = stack.empty() ? height.length : height.length - stack.peek() - 1;
area = Math.max(area, height[start] * width);
}
return area;
}
}

• Your code returns the correct output `8` for the input `[3,1,3,4,2,3]`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.