LeetCode – 84. Largest rectangle in bar chart

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

84. Largest rectangle in a bar chart

N non-negative integers are given to represent the heights of the columns in a bar graph. Each column is adjacent to each other and has a width of 1.

Find the maximum area of rectangles that can be outlined in the bar chart.

As shown above, the resulting rectangle is the red rectangle in the figure, which has an area of 10.

Answer:

According to the above, the easiest way to think of, is the violence to solve: through each element of the array, then this element as a starting point, respectively to the left and right eyes, know is lower than the element of the pillars, then found a height of the current element height, width is about extending the sum of distance and a width of the rectangular element itself. By doing this for each element, comparing and calculating, you get the maximum value.

This method is equivalent to two levels of traversal of the array, O(n^2). We need to find the optimized space. The problem with the above solution is that a lot of data is not retained in the process of traversing the array, resulting in each traversal of an element requiring the entire array to find the width of the large area outlined by the current element height. We can record the data in the traversal process through the way of space for time to realize the optimization of time complexity.

First, iterate through the array again, determining the left and right boundaries of the rectangle that can be drawn by the height of the current element.

For example, when traversing to the column with subscript 0, the height is 2. Since there are no other elements to the left of the column, its left side is determined. However, since the height of the column behind is not known, the right boundary cannot be confirmed. It then traverses the column of subscript 1, whose height is 1, which is less than 2. At this point, the right edge of the rectangle that can be drawn by the column of height 2 is confirmed. At this point, you don’t have to worry about the column of height 2.

But the right boundary of the column of height 1 is still uncertain and needs to be traversed backwards. By repeating the above backward traversal and height comparison process, we can find that, assuming the currently convenient column with index curr, when the column with index curr + 1 is higher than curr, we cannot determine the right side of curr, but when it is lower, The right boundary of all previous columns higher than curr + 1 is now confirmed.

Therefore, convenient in our pillar height in the process, if the curr + 1 is higher than curr, we recorded, if lower, then from previous record to find it in the height of the left boundary, when the height of the curr can sketch out the area of the rectangle is confirmed and calculate it, was cleared from our records in the data.

So all the columns that we record, their height is increasing. (In the convenient process, if the column is getting higher and higher, write it down; if it is getting lower, find the higher column in front, calculate their corresponding result, and make clear), and, if the column is recorded later, the area of the rectangle will be confirmed earlier, that is, last in first out. Thus, the data structure in which we record data is a monotonous stack.

Finally, after all the elements are convenient and the area of the rectangle outlined by their height is calculated, the maximum value of the comparison is finally obtained.

In addition, in order to simplify the calculation, we can add a column with a height of 0 at the beginning and end of the array, which can avoid the trouble of judgment and does not affect the result.

Final code:

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return heights[0];
        }
        int[] newHeights = new int[n + 2];
        System.arraycopy(heights, 0, newHeights, 1, n);
        heights = newHeights;
        n += 2;
        int max = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 1; i < n; i++) {
            while (heights[stack.peek()] > heights[i]) {
                int h = heights[stack.pop()];
                while(! stack.isEmpty() && heights[stack.peek()] == h) { stack.pop(); }int w = i - stack.peek() - 1;
                max = Math.max(max, w * h);
            }
            stack.push(i);
        }
        returnmax; }}Copy the code