3ms Java solution starting from a bruteforce algorithm


  • 0
    J

    I started with O(n²) bruteforce algorithm, which of course exceeded time limit, but ended up with a solution of 3ms after a few modifications. The point is you can skip a lot of iterations from the outer loop (look at the if statements), and the inner loop should go backward.

    public int maxArea(int[] height) {
        int n = height.length;
        if (n < 2) return 0;
        if (n == 2) return Math.min(height[0], height[1]);
            
        int maxArea = 0;
        int maxHeight = 0;
        for (int i = 0; i < n - 1; i++) {
            if (height[i] < maxHeight || height[i] * (n-i) < maxArea)
                continue;
            maxHeight = height[i];
            for (int j = n - 1; j > i; j--) {
                int area = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, area);
                if (height[j] >= height[i]) break;
            }
        }
        return maxArea;
    }

Log in to reply
 

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