Beats 93%, Java, no stack


  • 1
    N

    thanks to @zerobased, the idea of copying heights to another array with one more element is great.

    public int largestRectangleArea(int[] heights) {
            // The basic idea is below:
            // if (heights[i] <= heights[i + 1]), continue. Because the area contains heights[i + 1] will definitely larger than heights[i].
            
            
            // copy the array, the idea copies from @zerobased
            int[] newHeights = new int[heights.length + 1];
            
            // newHeights[newHeights.length - 1] = 0, easier to handle the edge cases.
            for (int i = 0; i < heights.length; i++) {
                newHeights[i] = heights[i];
            }
            
            int res = 0;
            
            for (int i = 0; i < newHeights.length - 1; i++) {
                if (newHeights[i] <= newHeights[i + 1]) {
                    continue;
                }
                
                int lowest = newHeights[i];
                
                for (int j = i; j >= 0; j--) {
                    lowest = Math.min(lowest, newHeights[j]);
                    int area = lowest * (i - j + 1);
                    res = Math.max(res, area);
                }
            }
            
            return res;
            
        }

  • 0
    A

    I don't understand why this solution is so fast. It seems an O(n^2) to me. I used a stack and an O(n) solution but is far slower than this one. Could anyone explain to me?


Log in to reply
 

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