This is the 10th day of my participation in the August More Text Challenge. For details, see:August is more challenging

The largest rectangle in the bar chart (Question Number 84)

The title

Given n non-negative integers, denote the height of each column in a bar chart. Each column is adjacent to each other and has a width of 1.

Find the maximum area of the rectangle that can be delineated in the bar chart.

Example 1:

Enter: heights = [2.1.5.6.2.3] output:10Interpretation: The largest rectangle is the red area with an area of10
Copy the code

Example 2:

Enter: heights = [2.4] output:4
Copy the code

Tip:

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104

link

Leetcode-cn.com/problems/la…

explain

Oh, this one. This one is out of the question.

To tell you the truth, when I see this problem, my first feeling is DP, using DP [I][j] to represent the lowest height in the interval from I to j. Indeed, this idea is feasible, but it will time out, because it requires two for loops, the time complexity is O(nlogn), and the details will be explained in the answer. Here is the main introduction to the official solution of AC.

Let’s take the official first chestnut for a good analysis, and take a look at this picture 👇 :

If you want to get to the most large areas of content, you will need to find a N column column in a row, the left and right sides of the columns must is smaller than the continuous column border, in the chestnut, continuous column is 5 and 6, and on the left side of the 1 and 2 are smaller than the border on the right side of the, if extended to 1, then the area of continuum is 3 * 1, 3, It’s obviously less than 5 times 2.

May draw a conclusion from the above derivation, a range of maximum is determined by the two boundary values, as if to say like don’t say, but that is the key point and here from 2 to 1, and can find it in a smaller area, because of the boundary value becomes so at this time should be calculated under the current the most large area, you can get 2, that from 6 to 2, In this case, we should calculate the previous maximum matrix value and get 10. In the subsequent operation, we can also continue. If we encounter a value larger than the boundary value, we will not do statistics, and if we encounter a value smaller than the boundary value, we will start to calculate the previous maximum area.

So what’s the maximum area? Calculate the value where the current value is larger than the previous value. For example, if we encounter a 2 after 6, the value greater than 2 in the previous value is 1. Therefore, the current statistical area should be the maximum area of the columns 5 and 6.

So how do you solve the maximum value of the first two columns and the last two columns? It is possible to add two columns of zero height at the edge of the start and end positions, and not only will the original column be counted, but the last column will also go through a calculation because there are other columns lower than its own height behind it.

So that’s the whole idea. Let’s look at the code.

Your own method (traversal)

The overall logic is similar to what is explained in the explanation. The code 👇 :

var largestRectangleArea = function(heights) {
  const len = heights.length
  let active = null
  let res = 0
  for (let i = 0; i < len; i++) {
    res = Math.max(res, heights[i])
    for (let j = i; j < len; j++) {
      if (i === j) {
        active = heights[i]
      } else {
        active = Math.min(active, heights[j])
        res = Math.max((j - i + 1) * active, res)
      }
    }    
  }
  return res
};
Copy the code

Here we directly look at the results after the final optimization. We use active to store the results of last time, that is, the minimum height of i-1 and j. However, due to the high time complexity of this method, we finally run to GG in the 92nd test case.

As it did not pass, I will not go into details here.

Better Approach (stack)

As explained in the explanation, we need to record the height of the current column and the height of the previous column, so it is obvious that the stack is a reasonable data structure.

Whenever you come to a new column, determine whether the column is higher than the top column of the stack. If it is higher, push it directly into the stack to become the new top element. If it is lower than the top element, the current top element is removed and the maximum size of the top element is calculated.

Note to remove the stack elements of a while loop operation, because may be removed after, new stack elements or higher than the current level, so the need for a continuous operation, and after each operation to recalculate the possible maximum, after each operation, according to the index, can make the width of 1.

👇 is the code:

function largestRectangleArea(heights) {
  heights = [0. heights,0]
  let res = 0
  const stack = []
  for (let i = 0; i < heights.length; i++) {
    while (heights[i] < heights[stack[stack.length - 1]]) {
      const activeHeight = stack.pop()
      res = Math.max(
        res,
        heights[activeHeight] * (i - stack[stack.length - 1] - 1)
      )
    }
    stack.push(i)
  }
  return res
}
Copy the code

This whole logic is a little convoluted, and I can’t really understand it so I can type in a couple of logs.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)