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;
}
}
Last updated