Day60 单调栈 part03

最后一天啦！完结撒花~

84.柱状图中最大的矩形

我的思路：
感觉和接雨水差不多，只需要多考虑一些情况

双指针
lheight 和 rheight 分别是用来存储每个柱子的左边界和右边界的数组。

解答：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        int[] lheigth = new int[heights.length];
        int[] rheight = new int[heights.length];
        for(int i = 0; i < heights.length; i++) {
            int j = i - 1;
            while(j >= 0 && heights[j] >= heights[i]) {
                j = lheigth[j];
            }
            lheigth[i] = j;
        }
        for(int i = heights.length - 1; i >= 0; i--) {
            int  j = i + 1;
            while(j < heights.length && heights[j] >= heights[i]) {
                j = rheight[j];
            }
            rheight[i] = j;
        }
        for(int i = 0; i < heights.length; i++) {
            int h = heights[i];
            int w = rheight[i] - lheigth[i] - 1;
            res = Math.max(res, h * w);
        }
        return res;
    }
}

单调栈

解答：

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int n = heights.length;
        for(int i = 0; i <= n; i++) {
            int currheight = (i == n) ? 0 : heights[i];
            while(!stack.isEmpty() && currheight < heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int distance = stack.isEmpty() ? i : i - stack.peek() - 1;
                res = Math.max(res, distance * h);
            }
            stack.push(i);
        }
        return res;
    }
}