LeetCode——largest-rectangle-in-histogram

Q：给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积

上图是每条宽度为1, 高度 =[2,1,5,6,2,3].的直方图

图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位
例如：
给出的高度 =[2,1,5,6,2,3],
返回10.

A：遍历数组以当前值为高构建最大长方形。
用堆栈计算每一块板能延伸到的左右边界
对每一块板

• 堆栈顶矮，这一块左边界确定，入栈
• 堆栈顶高，堆栈顶右边界确定，出栈，计算面积
• 入栈时左边界确定
• 出栈时右边界确定
• 堆栈里元素是递增的（内部保持升序）

本质：中间的短板没有用！
复杂度 O(n)

public int largestRectangleArea(int[] height) {
        int n = height.length;
        int result = 0;
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!s.empty() && height[s.peek()] >= height[i]) {
                int index = s.pop();
                int h = height[index];
                int k = i - 1 - (s.empty() ? (-1) : s.peek());
                result = Math.max(result, k * h);
            }
            s.push(i);
        }
        while (!s.empty()) {
            int index = s.pop();
            int h = height[index];
            int k = n - 1 - (s.empty() ? (-1) : s.peek());
            result = Math.max(result, k * h);
        }
        return result;
    }

LeetCode——largest-rectangle-in-histogram

原文：https://www.cnblogs.com/xym4869/p/12636512.html