84-largest-rectangle-in-histogram.md

84. Largest Rectangle in Histogram - 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

 

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

 

示例:

输入: [2,1,5,6,2,3]
输出: 10

---

题目标签：Stack / Array

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
java	13 ms	40.6 MB

class Solution {
    class Node {
        int index;
        int value;
        Node(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }
    
    public int largestRectangleArea(int[] heights) {
        Stack<Node> stk = new Stack<>();
        int[] left = new int[heights.length];
        Arrays.fill(left, -1);
        for (int i = heights.length - 1; i >= 0; i--) {
            while (!stk.empty() && heights[i] < stk.peek().value) {
                left[stk.pop().index] = i;
            }
            stk.push(new Node(i, heights[i]));
        }
        //for (int i : right) System.out.print(i + " "); System.out.println();
        stk.clear();
        int[] right = new int[heights.length];
        Arrays.fill(right, heights.length);
        for (int i = 0; i < heights.length; i++) {
            while (!stk.empty() && heights[i] < stk.peek().value) {
                right[stk.pop().index] = i;
            }
            stk.push(new Node(i, heights[i]));
        }
        //for (int i : right) System.out.print(i + " "); System.out.println();
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
}