TLE for test case 3000 consecutive 1s


  • 10
    A

    It passes the custom testcase in 24ms, but when I submit it's TLE..

    Code:

    public class Solution {
        public int largestRectangleArea(int[] height) {
            Stack<Integer> maxIdx = new Stack<Integer>();
            int area = 0;
            for (int i = 0; i < height.length; i++) {
                if (maxIdx.isEmpty() || height[maxIdx.peek()] <= height[i]) {
                    maxIdx.push(i);
                } else {
                    int idx = maxIdx.pop();
                    int width = maxIdx.isEmpty() ? i : i - maxIdx.peek() - 1;
                    area = Math.max(area, width * height[idx]);
                    i--;
                }
            }
            while(!maxIdx.isEmpty()) {
                int idx = maxIdx.pop();
                int width = maxIdx.isEmpty() ? height.length : height.length - maxIdx.peek() - 1;
                area = Math.max(area, width * height[idx]);
            }
        return area;
        }
    }
    

    Thanks!


  • 0
    J

    The original ac code got tle too..


  • 0

    Thanks for reporting this issue, your solution should get Accepted now.


Log in to reply
 

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