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

First, understand the topic

84. Largest rectangle in 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.

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

Ii. Solution analysis

The problem is solved in a stack. So let’s look at the steps to solve the problem, as follows:

  • Define a stack for storing data larger than the previous one.
  • traverseheight, when the data is larger than the previous data, the operation of pushing is performed;
  • Otherwise, the area is calculated.

Three, code implementation

Based on the above solution, we will use JS to implement this problem. The specific implementation code is as follows:

/ * * *@param {number[]} heights
 * @return {number}* /
​
const largestRectangleArea = (heights) = > {
    // 1. Define a variable to store the maximum size
    let maxArea = 0;
    // 2. Define a stack to store data larger than the previous one
    const stack = [];
    // 3. Add a 0 before and after the rectangle, so that the rectangle can be properly added to the stack
    heights = [0. heights,0];
    // 4
    for (let i = 0; i < heights.length; i++) {
        // 4.2 If the number is smaller than the previous number, the comparison shall be made. If the number is higher than the previous number, the comparison shall not be made
        // Why? Because still in the race, also don't know if there are higher
        while (heights[i] < heights[stack[stack.length - 1]]) {
            The top element is removed from the stack and the index of the top element is saved
            const stackTopIndex = stack.pop();
            // Calculate the rectangle area formed by the bar of the stack and compare it with the previous maximum area
            maxArea = Math.max(
                maxArea,
                heights[stackTopIndex] * (i - stack[stack.length - 1] - 1) // i-stack [stack.length-1] is the current index minus the value of the last element in the stack minus 1)}4.1 If the value is larger than the previous value, the stack operation is performed
        stack.push(i);
    }
    // 5. Return the result
    return maxArea;
}
​
console.log(largestRectangleArea([2.1.5.6.2.3])); / / 10
Copy the code

Iv. Process review

Finally, we use a graph to describe all the processes of the whole problem. The details are as follows: 👇

The above is about the problem solution, I do not know whether it is helpful to small friends?

We’ll see you next time at 👋👋👋