Skip to content

Latest commit

 

History

History
131 lines (119 loc) · 3.71 KB

84. Largest Rectangle in Histogram.md

File metadata and controls

131 lines (119 loc) · 3.71 KB

84. Largest Rectangle in Histogram

leetcode Daily Challenge on December 31th, 2020.

Difficulty : Hard

Related Topics : Array、Stack

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

1

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

2

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Solution

  • mine
    • Java
      • Runtime: 596 ms, faster than 16.87%, Memory Usage: 41 MB, less than 77.27% of Java online submissions 
        // O(N^2)time  
// O(1)space
public int largestRectangleArea(int[] heights) {
    int res = 0;
    int len = heights.length;
    if(len == 0){
        return res;
    }
    for(int i = 0; i < len; i++){
        int t = heights[i];
        for(int j = i; j >= 0; j--){
            if(heights[j] < t){
                t = heights[j];
            }
            res = Math.max(res, t * (i - j + 1));
        }
    }
    return res;
}
  • the most votes

  • Runtime: 1 ms, faster than 99.80%, Memory Usage: 41 MB, less than 75.00% of Java online submissions

    //O(N)time  O(N)space
public int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int[] lessFromLeft = new int[height.length]; // idx of the first bar the left that is lower than current
    int[] lessFromRight = new int[height.length]; // idx of the first bar the right that is lower than current
    lessFromRight[height.length - 1] = height.length;
    lessFromLeft[0] = -1;

    for (int i = 1; i < height.length; i++) {
        int p = i - 1;

        while (p >= 0 && height[p] >= height[i]) {
            p = lessFromLeft[p];
        }
        lessFromLeft[i] = p;
    }

    for (int i = height.length - 2; i >= 0; i--) {
        int p = i + 1;

        while (p < height.length && height[p] >= height[i]) {
            p = lessFromRight[p];
        }
        lessFromRight[i] = p;
    }

    int maxArea = 0;
    for (int i = 0; i < height.length; i++) {
        maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
    }

    return maxArea;
}

  • Runtime: 11 ms, faster than 36.39%, Memory Usage: 46.5 MB, less than 6.82% of Java online submissions

    //O(N)time  O(N)space
public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(right, n);

    LinkedList<Integer> mono_stack = new LinkedList<Integer>();
    for (int i = 0; i < n; ++i) {
        while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
            right[mono_stack.peek()] = i;
            mono_stack.pop();
        }
        left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
        mono_stack.push(i);
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
    }
    return ans;
}