84.Largest-Rectangle-in-Histogram

84. Largest Rectangle in Histogram

题目地址

https://www.lintcode.com/problem/largest-rectangle-in-histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/

题目描述

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.

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

代码

Approach #1 Brute Force

Time: O(n^2) Space O(1)

public class Solution {
  public int largestRectangleArea(int[] heights) {
    int maxarea = 0;
    for (int i = 0; i < heights.length; i++) {
      int minheight = Integer.MAX_VALUE;
      for (int j = i; j < heights.length; j++) {
        minheight = Math.min(minheight, heights[j]);
        maxarea = Math.max(maxarea, minheight * ( j - i + 1));
      }
    }
    return maxArea;
  }
}

Approach #2: Divide and Conquer

public class Solution {
  public int largestRectangleArea(int[] heights) {
    return calculateArea(heights, 0, heights.length - 1);
  }

  public int calculateArea(int[] heights, int start, int end) {
    if (start > end) return 0;
    int minindex = start;
    for (int i = start; i <= end; i++) {
      if (heights[minindex] > heights[i]) {
        minindex = i;
      }
    }

    return Math.max(heights[minindex] * (end - start + 1),
                      Math.max(calculateArea(heights, start, minindex - 1), 
                               calculateArea(heights, minindex + 1, end)));
  }
}

Approach 3: Better Divde and Conquer

class Solution {
    class SegTreeNode {
        int start;
        int end;
        int min;
        SegTreeNode left;
        SegTreeNode right;
        SegTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            left = right = null;
        }
    }

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) return 0;
        SegTreeNode root = buildSegmentTree(heights, 0, heights.length - 1);

        return calculateMax(heights, root, 0, heights.length - 1);
    }

    int calculateMax(int[] heights, SegTreeNode root, int start, int end){
        if (start > end) return -1;
        if (start == end) return heights[start];

        int minIndex = query(root, heights, start, end);
        int leftMax = calculateMax(heights, root, start, minIndex - 1);
        int rightMax = calculateMax(heights, root, minIndex + 1, end);
        int minMax = heights[minIndex] * (end - start + 1);
        return Math.max(Math.max(leftMax, rightMax), minMax);
    }

    SegTreeNode buildSegmentTree(int[] heights, int start, int end) {
        if (start > end) return null;
        SegTreeNode root = new SegTreeNode(start, end);
        if (start == end) {
            root.min = start;
            return root;
        } else {
            int middle = (start + end) / 2;
            root.left = buildSegmentTree(heights, start, middle);
            root.right = buildSegmentTree(heights, middle + 1, end);
            root.min = heights[root.left.min] < heights[root.right.min] ? root.left.min : root.right.min;
            return root;
        }
    }

    int query(SegTreeNode root, int[] heights, int start, int end) {
        if (root == null || end < root.start || start > root.end) return -1;
        if (start <= root.start && end >= root.end) {
            return root.min;
        }

        int leftMin = query(root.left, heights, start, end);
        int rightMin = query(root.right, heights, start, end);
        if (leftMin == -1) return rightMin;
        if (rightMin == -1) return leftMin;
        return heights[leftMin] < heights[rightMin] ? leftMin : rightMin;
    }

}

Approach 4: Using Stack 单调递增栈

public class Solution {
  public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(-1);
    int maxarea = 0;
    for (int i = 0; i < heights.length; i++) {
      while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
        maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
      }
      stack.push(i);
    }
    while (stack.peek() != -1) {
      maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() - 1));
    }

    return maxarea;
  }
}