代码随想录训练营第60天|84.柱状图中最大的矩形

84.柱状图中最大的矩形

文章

代码随想录|0084.柱状图中最大的矩形

思路

用两个数组分别维护每个位置左边第一个比该位置高度低的下标和右边第一个比该位置高度低的下标
遍历每个位置，则包含该位置的最大矩形面积为$height[i]\ast (right[i]-left[i]-1)$
维护遍历过程中的最大面积，最后返回

代码

、class Solution {
    public int largestRectangleArea(int[] heights) {
        int ans = 0;
        Deque<Integer> dq = new LinkedList<>();
        int i, n;
        n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        for (i = 0; i < n; ++i) {
            while (!dq.isEmpty() && heights[i] < heights[dq.peek()]) {
                right[dq.pop()] = i;
            }
            dq.push(i);
        }
        // for (i = 0; i < n; ++i) {
        //     if (right[i] < n)
        //         System.out.print(" " + heights[right[i]]);
        //     else
        //         System.out.print(" " + n);
        // }
        dq.clear();
        System.out.println();
        for (i = n - 1; i > -1; --i) {
            while (!dq.isEmpty() && heights[i] < heights[dq.peek()]) {
                left[dq.pop()] = i;
            }
            dq.push(i);
        }
        for (i = 0; i < n; ++i) {
            ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));
            // System.out.println(" " + heights[i] + ", " + right[i] + ", " + left[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结

想了好久才想到要用两个数组
卡哥文章里只用了一个数组的方法还要再看看