LeetCode 84. Largest Rectangle in Histogram 直方图最大矩形覆盖

题目

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

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.

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

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

Example:

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

讲解

我们引入一个栈来解决这个问题。首先,把一个假的索引-1推进栈里面。然后依次加入数组中的索引,当出现两个连续高度下降的柱子时候,我们开始取出栈顶索引比计算矩形面积,直到heights[stack.peek()] ≤ heights[i],计算矩形面积:heights[stack.pop()] * (i − stack.peek() − 1)。

视频教学

Java代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        
        for (int i = 0; i < heights.length; i++) {
            int currentBarHeight = heights[i];
            
            while (stack.peek() != -1 && currentBarHeight <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                
                int area = height * width;
                maxArea = Math.max(area, maxArea);
            }          
            
            stack.push(i);
        }
        
        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            
            int area = height * width;
            maxArea = Math.max(area, maxArea);
        }
        
        return maxArea;
        
        // Time complexity : O(n). n numbers are pushed and popped.
        // Space complexity : O(n). Stack is used.
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注