This solution gets a TLE.

```
public class Solution {
public int largestRectangleArea(int[] heights) {
if ( heights.length < 0 ) { return 0; }
int maxArea = 0;
Deque<Integer> stack = new LinkedList<Integer>();
// make sure when the loop end, stack is empty
for ( int i = 0; i <= heights.length; i++ ) {
// the last 0 value height ensure the stack get empty
int height = (i == heights.length) ? 0 : heights[i];
while ( !stack.isEmpty() && heights[stack.peek()] >= height ) {
int j = stack.pop();
int right = i, left = stack.isEmpty() ? 0 : stack.peek()+1;
int area = heights[j] * (right-left);
maxArea = Math.max(maxArea, area);
}
stack.push(i); // every bar enter the stack exactly once
}
return maxArea;
}
}
```

And then I change the while loop condition from `heights[stack.peek()] >= height`

to `heights[stack.peek()] > height`

, the solution get accepted. I am a little bit confused. Here are the AC solution with that one conditions change.

```
public class Solution {
public int largestRectangleArea(int[] heights) {
if ( heights.length < 0 ) { return 0; }
int maxArea = 0;
Deque<Integer> stack = new LinkedList<Integer>();
// make sure when the loop end, stack is empty
for ( int i = 0; i <= heights.length; i++ ) {
// the last 0 value height ensure the stack get empty
int height = (i == heights.length) ? 0 : heights[i];
while ( !stack.isEmpty() && heights[stack.peek()] > height ) {
int j = stack.pop();
int right = i, left = stack.isEmpty() ? 0 : stack.peek()+1;
int area = heights[j] * (right-left);
maxArea = Math.max(maxArea, area);
}
stack.push(i); // every bar enter the stack exactly once
}
return maxArea;
}
}
```

The test case causes the TLE is [1,1,1,1......,1,1,1,1,1,1] (lots of ones). In the AC solution, all the element in the heights array will all get push into the stack and won't be pop out until i becomes heights.length. In contrast, in the first solution, the stack will stay small. Why the second solution outperforms the first one?