Java Solution AC in 5ms


  • 0
    R
    1. scan the array twice
      2.use auxiliary array to store each left and right smaller index.
      3.combine the left & right part to gather the max area with the bar
    public static int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int[] leftStart = new int[n];
            int[] rightStart = new int[n];
            leftStart[0] = 0;
            for (int i = 1; i < n; i++) {
                leftStart[i] = i;
                int nextLeft = i - 1;
                while (nextLeft >= 0 &&
                        heights[nextLeft] >= heights[i]) {
                    leftStart[i] = leftStart[nextLeft];
                    nextLeft = leftStart[nextLeft] - 1;
                }
            }
            rightStart[n - 1] = n - 1;
            int max = (n - leftStart[n - 1]) * heights[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                rightStart[i] = i;
                int nextRight = i + 1;
                while (nextRight < n &&
                        heights[nextRight] >= heights[i]) {
                    rightStart[i] = rightStart[nextRight];
                    nextRight = rightStart[nextRight] + 1;
                }
                int iMax = (i - leftStart[i] + 1) * heights[i] +
                        (rightStart[i] - i + 1) * heights[i] - heights[i];
                if (iMax > max) {
                    max = iMax;
                }
            }
    
            return max;
        }
    

Log in to reply
 

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