Clear Divide and Conquer Java 17ms


  • 0
    Y
    class Solution {
        public int getArea(int[] heights, int left, int right) {
            if (left == right) {
                return heights[left];
            }
            int mid = (left + right) / 2;
            // left max area
            int leftArea = mid-1 < left ? 0 : getArea(heights, left, mid-1);
            // right max area
            int rightArea = mid+1 > right ? 0 : getArea(heights, mid+1, right);
            // mid max area, including current bar
            int i = mid, j = mid;
            int width, midArea = 0;
            int height = heights[mid];
            while (i >= left && j <= right) {
                width = j - i + 1;
                height = Math.min(height, Math.min(heights[i], heights[j]));
                midArea = Math.max(midArea, width * height);
                if (i == left) {
                    j += 1;
                } else if (j == right) {
                    i -= 1;
                } else if (heights[i-1] >= heights[j+1]) {
                    i -= 1;
                } else {
                    j += 1;
                }
            }
            return Math.max( midArea, Math.max(leftArea, rightArea) );
        }
        public int largestRectangleArea(int[] heights) {
            return heights.length == 0 ? 0 : getArea(heights, 0, heights.length-1);
        }
    }
    

Log in to reply
 

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