image.png

解法

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];
        Stack<Integer> s = new Stack();
        // 找出每一个元素左侧第一个小于它的元素的下标
        for (int i = 0; i < len; i++) {
            while (!s.isEmpty() && heights[s.peek()] >= heights[i]) {
                s.pop();
            }
            left[i] = s.isEmpty() ? -1 : s.peek();
            s.push(i);
        }
        s.clear();
        // 找出每个元素右侧第一个大于它的元素的下标
        for (int i = len - 1; i >= 0; i--) {
            while (!s.isEmpty() && heights[s.peek()] >= heights[i]) {
                s.pop();
            }
            right[i] = s.isEmpty() ? len : s.peek();
            s.push(i);
        }
        int res = 0;
        for (int i = 0; i < len; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }
}

一遍求左右边界的解法，这种就是有一个高有准确值就行。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];
        // 默认右侧都是哨兵，到最大值
        Arrays.fill(right, len);
        Stack<Integer> s = new Stack();
        for (int i = 0; i < len; i++) {
            while (!s.isEmpty() && heights[s.peek()] >= heights[i]) {
                // 这里相等的情况下并不准确，但最右边那个是准确的就够了
                // 就可以去算最大值了
                right[s.peek()] = i;
                s.pop();
            }
            left[i] = s.isEmpty() ? -1 : s.peek();
            s.push(i);
        }
        int res = 0;
        for (int i = 0; i < len; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }
}