0084. Largest Rectangle in Histogram (H)

题目

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

题意

在直方图中找到面积最大的矩形。

思路

参考[LeetCode] 84. Largest Rectangle in Histogram 直方图中最大的矩形以及LeetCode 笔记系列 17 Largest Rectangle in Histogram。

代码实现

Java

class Solution {
    public int largestRectangleArea(int[] heights) {
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        int i = 0;
        int[] copy = Arrays.copyOf(heights, heights.length + 1);
        while (i < copy.length) {
            if (stack.isEmpty() || copy[i] > copy[stack.peek()]) {
                stack.push(i++);
            } else {
                int h = copy[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                ans = Math.max(ans, h * w);
            }
        }
        return ans;
    }
}