This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

The title

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.

Example 1

Input: heights = [2,1,5,6,2,3] output: 10 description: the largest rectangle is the red area in the figure with an area of 10Copy the code

Example 2

Heights = [2,4] output: 4Copy the code

Train of thought

So they’re trying to figure out the maximum area of a rectangle, and the formula for the area is height times width, and the obvious thing to think about is, if you can fix something like height, and try to increase width, you’re going to get bigger and bigger rectangles.

However, there is a problem with this problem. As the height decreases, the width will increase, and the size of the area will be uncertain.

Another way to think about it: If you can’t determine height or width, try determining a boundary. For example, determine the left boundary, and then enumerate the right boundary, calculate the maximum area in the process; There is a violent solution

Violent solution complete code

    / * * *@param {number[]} heights
     * @return {number}* /
    var largestRectangleArea = function (heights) {
        const n = heights.length;
        let maxArea = 0;

        // enumerate the left boundary
        for(let i = 0; i < n; i++) {
            // Define the minimum height as the maximum
            let minHeight = Number.MAX_VALUE;

            // enumerate the right boundary
            for(let j = i; j < n; j++) {

                // If the height of the right boundary is 0 and the previous block does not form a rectangle, exit the right boundary enumeration
                if(heights[j] == 0) {
                    break;
                }

                // The minimum height in the process
                minHeight = Math.min(minHeight, heights[j]);

                // Compare the area
                maxArea = Math.max(maxArea, minHeight * (j - i + 1)); }}return maxArea;
    };
Copy the code

The time complexity of the violent solution, O(n ^ 2), still fails LeetCode’s submission test, 😅 ~ ~

Official solution: monotone stack

Waiting for updates: 😭 (see efforts to understand)

    const largestRectangleArea = (heights) = > {
        let maxArea = 0
        const stack = []
        heights = [0. heights,0]
        for (let i = 0; i < heights.length; i++) {
            while (heights[i] < heights[stack[stack.length - 1]]) { // The current bar is shorter than the top bar
                const stackTopIndex = stack.pop() // The top element is removed from the stack, and the index of the top bar is saved
                maxArea = Math.max(               // Calculate the area and challenge the maximum area
                    maxArea,                        // Calculate the rectangle area formed by the stack bar
                    heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)
                )
            }
            stack.push(i)                       // The current bar is higher than the top bar of the stack
        }
        return maxArea
    }
Copy the code

summary

The violent solution is usually the most common idea, based on the most common public, common sense, etc., by giving examples of all possible answers and then finding the one that best fits the question

But often violent solution time complexity is very high, need to optimize a lot of unnecessary calculations or according to some conclusions to cheat, skill is often very high!

If there is no more optimized solution, the algorithm is not enough!

LeetCode 👉 HOT 100 👉 The largest rectangle in the bar chart – medium item ✅

Collection: LeetCode 👉 HOT 100, will update when you are free, we support a lot, click a like 👍

If you have a good solution or find something wrong with this article, please leave a comment at 😄