84. 柱状图中最大的矩形

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/submissions/
左右指针优化法：

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 时间：O（N）
        int length = heights.length;
        int maxArea = 0;
        int[] leftBound = new int[length];
        int[] rightBound = new int[length];
        for (int i = 0; i < length; i++) {
            int height = heights[i];
            int left = i - 1;
            // 左指针左移，寻找边界
            while (left >= 0) {
                if (heights[left] < height) break;
                // 如果左边柱子更高，就直接跳到它的左边界柱子再判断
                left = leftBound[left];
            }
            leftBound[i] = left;
        }
        for (int i = length - 1; i >= 0; i--) {
            int height = heights[i];
            int right = i + 1;
            // 右指针右移，寻找边界
            while (right < length) {
                if (heights[right] < height) break;
                // 如果右边柱子更高，就直接跳到它的右边界柱子再判断
                right = rightBound[right];
            }
            rightBound[i] = right;
        }
        // 遍历所有柱子，计算面积
        for (int i = 0; i < length; i++) {
            int curArea = (rightBound[i] - leftBound[i] - 1) * heights[i];
            maxArea = Math.max(maxArea,curArea);
        }
        return maxArea;
    }
}

单调栈优化法

class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int maxArea = 0;
        int[] leftBound = new int[length];
        int[] rightBound = new int[length];
        for (int i = 0; i < length; i++) {
            rightBound[i] = length;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        // 遍历所有柱子，作为当前高度
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                // 当前元素的高度小于栈顶元素，那么此时其右边界就是当前元素
                rightBound[stack.peek()] = i;
                stack.pop();
            }
            // 所有大于等于当前高度的元素全部弹出，找到了左边界
            leftBound[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        for (int i = 0; i < length; i++) {
            int curArea = (rightBound[i] - leftBound[i] - 1) * heights[i];
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }
}