I encounter a Weird Time Limited Errors


  • 0

    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?


Log in to reply
 

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