This article originated from personal public account: TechFlow, original is not easy, for attention


Largest Rectangle in Histogram (Largest Rectangle area)

The official difficulty of this question is Hard, with 3,581 upvotes and only 80 downvotes, with a pass rate of around 34.7%. In terms of the pass rate, the difficulty is actually ok, not particularly big, but this question has a very high “like” ratio, indicating that the quality of the question is very good. In fact, it is. It’s a classic, and I highly recommend it. Suggest everybody has ability to do this question, certain meeting has harvest very much.

The question

Suppose we have a series of rectangles with the same width of 1 placed vertically together, what is the maximum area that this pattern can cover?


For example, in the figure above, we have six rectangles with a width of 1. The largest rectangle we can find should be the rectangle enclosing the middle 5 and 6:


Given a number of integers representing the heights of these rectangles, it is asked to return the area of the largest rectangle that can be found.

The sample

Input: [2,1,5,6,2,3]
Output: 10
Copy the code

Evaluate the interval

We should feel the difficulty of this problem in our hands. We did not have any good ideas at the beginning, and the topic was quite clear. There were not too many points to analyze. So let’s think about the simplest solution.

The easiest way to do this is to find all the rectangles you can make, and then compare the areas between them to find the largest area. It’s easy to imagine that we can iterate over the starting position of the rectangle, and that gives us the width of the rectangle. The length of the rectangle is simply the lowest height in the selected interval.


We can do a little bit of a mental shift, assuming that these rectangles are strips of wood, and we want to pick the strips to make the bucket. So according to the bucket effect, the height of the water enclosed by the bucket depends on the shortest bar, and the height of the area enclosed by the rectangle depends on the shortest of these rectangles. In other words, once we’ve determined the interval, all we need to do is find the smallest number in the interval. So this becomes an interval optimization problem, for example in the figure above, if we choose the last three rectangles, then its height is 2.

Let’s say there are n rectangles to choose from, and the combinations we can pick are going to beIt’s about n squared. For each interval, we need to iterate over the elements in them to get the minimum, and that requiresSo the overall complexity should beOrders of magnitude. Obviously, this is a very large order of magnitude, and when n goes beyond 1000 it’s very hard to figure out the solution.

This idea is obviously not good enough, and it’s not easy to optimize. For example, if you’ve learned about data structures like segment trees, you might even think about using segment trees, where we can optimize our queries to minimize each time, but even then the final complexity is high. And that’s because we’re going through the interval at the beginning and the end, which is difficult to optimize. soThe limits of this idea have been determined, and we can’t make big optimizations.

From this point on, if there’s a better solution, it’s not going to work that way.

Reverse thinking

One of the ideas above is unlikely, but it offers a positive way forward. We search all the intervals, and then determine the height of the rectangle by the bars in the interval, and we get the area of the rectangle.

Since this path is not going anywhere, can we think the other way around? Let’s suppose we find the answer, which is a rectangle of bars in the interval [A, B], and its height is h. So according to the barrel effect, one of the bars between A and B must be length H. For example, in the figure below, [5, 6, 2, 3] must be 2 if it is to be a rectangle.


In this case, we can look for the largest rectangle that can be formed with a particular bar as a short board. For example, if we look for the first bar, we can only find itself, so the area of the rectangle is 1 x 2 = 2. If you take the second bar as the short board, you can find the entire interval, and its corresponding area is 1 x 6 = 6.

Since we only have n strips, we must be able to find at most n rectangles by using each strip as a short board.The final answer must be one of these n rectanglesIn the positive thinking, we look for the interval needs of wooden barsWhile we’re looking for a weak spot, we just need toIn other words, there is less space to search, so as long as we can search efficiently, we can find the answer faster.

To find the largest rectangle for each bar, we need to find the farthest left and right side of each short board. In the example above, we can get [0, 5, 3, 3, 5, 5] based on how far each bar extends to the right. Similarly, we can get the array of each bar extending to the left: [0, 0, 2, 3, 2, 5]. With these two arrays, we can calculate the area of the largest rectangle with each bar as a short board, and the one with the largest area is the answer.

This position we can find using a monotonic stack, we use an ordered stack to maintain the extended position. For example, we maintain the position of each bar extending to the right with a monotone stack increasing from the bottom of the stack to the top. When we encounter a new bar, all the values in the stack longer than it pop up. For these values, the new bar is the right boundary. For example, [5, 6, 2], initially read 5, push. Then we read 6, and since 6 is larger than 5 at the top of the stack, 6 is pushed onto the stack. Finally, we read 2, and since 2 is smaller than 6, 6 goes off the stack, and for 6, the position of 2 is its right-hand boundary. It’s because 2 is smaller that it needs to go off the stack, which means that everything to the left of 2 is bigger than 6, otherwise 6 would have gone off the stack earlier. Likewise, 2 is the right-hand boundary of 5.

If you don’t know about monotone stacks, check out the previous article:

LeetCode42, monotony stack, construction, two Pointers. How many options do you have for this Hard problem?

If we flip the logic, we get the logic for the left edge. Once we have the left and right edges, we just multiply the length of the interval between them to get the area of the rectangle.

Next, we write the code:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
  The left edge is initialized to 0
        left_side = [0 for i in range(n)]
 The right edge is initialized to n-1  right_side = [n- 1 for _ in range(n)]   stack_left = []  stack_right = []   for i in range(n):  h = heights[i]  Pop all values in the stack that are smaller than the current element  # Note that subscripts are stored in the stack  while len(stack_right) > 0 and h < heights[stack_right[- 1]] : tail = stack_right[- 1]  stack_right.pop()  right_side[tail] = i - 1   The current element is pushed  stack_right.append(i)   # Flipping the coordinates is equivalent to traversing backwards  i_ = n - 1 - i  h = heights[i_]   Same logic for maintaining monotone stacks  while len(stack_left) > 0 and h < heights[stack_left[- 1]] : tail = stack_left[- 1]  stack_left.pop()  left_side[tail] = i_ + 1   The current element is pushed  stack_left.append(i_)    ret = 0  for i in range(n):  The area of the rectangle is equal to the right edge - the left edge +1 x height  cur = (right_side[i] - left_side[i] + 1) * heights[i]  ret = max(ret, cur)  return ret Copy the code

conclusion

If you want to solve this problem, it is useless to simply clarify the meaning of the question and to simply drab the stack. Not only do we need to clarify the meaning of the problem, deduce the optimization method from the simplest solution, but also need a deep understanding of the data structure of monotone stack, which can be flexibly applied.

Also, you need to pay special attention to boundaries in your code. Such as the setting of left and right boundaries during initialization, and the possibility of continuous equal elements, these need to be taken into account. While the code looks simple, it hides a lot of details, so it’s useless to just look at the code. It’s best to implement it yourself.

This is the end of today’s article, if you like this article, please invite a wave of quality sanlian, give me a little support (follow, forward, like).

This article is formatted using MDNICE