I encounter a Weird Time Limited Errors

• This solution gets a TLE.

``````public class Solution {
public int largestRectangleArea(int[] heights) {

if ( heights.length < 0 ) { return 0; }

int maxArea = 0;

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

// 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?

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