This is the sixth day of my participation in the First Challenge 2022

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Find the area of the largest rectangle in a histogram given n non-negative integers to represent the height of each column in the histogram.”

Title link:

Source: LeetCode

Link: 84. Largest rectangle in bar chart – Force buckle (LeetCode) (leetcode-cn.com)

2

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: Input: Heights = [2,4] Output: 4Copy the code

Second, the problem solving

1. Analysis of ideas

This problem is similar to 42 [catch rain], 42 is to find how much rain can be caught after the rain, this problem is to find the largest rectangle, why always pull out similar problems to talk about it, because this kind of problem will have similar ideas to solve the problem, can be reviewed after the solution.

The main methods to solve problem 42 [rain] are double pointer, monotonous stack, etc., this problem can also be used to solve the monotonous stack.

First of all, think about how to find the largest rectangle. Find a column and fix it as the height h of the rectangle. Then extend it left and right according to this column until it meets a column with a height less than H.

But in the determination of the width of the left and right traversal, time complexity is high, so at this time you can use monotone stack to optimize a repeat traversal.

OK, first of all, what is monotone stack, monotone stack is a very classical data structure, the data stored inside are ordered, can be divided into monotone increasing station and monotone decreasing stack, often used to solve the largest interval, the largest field of view, the largest rectangle, etc..

Take monotone increasing stack as an example. If the new element is larger than the top element, it is pushed. If smaller than the top of the stack, pop the element out until the top of the stack is smaller than the new element.

The advantage of this is that the elements in the stack are increasing, and when the element goes out of the stack, the new element is the smallest element after the element goes out of the stack, so that we can get the height of the left and right boundaries. Using monotone stack, we can get the left and right boundaries and calculate the area during the off stack operation.

2. Code implementation

Code reference:

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while(! mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) { mono_stack.pop(); } left[i] = (mono_stack.isEmpty() ?- 1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while(! mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) { mono_stack.pop(); } right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek()); mono_stack.push(i); }int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        returnans; }}Copy the code

3. Time complexity

Time complexity: O(N)

Space complexity: O(N)

Third, summary

1. For a column, the height is determined and its left and right boundaries are required.

2, according to the left and right boundary width, length multiplied by width can get the area

3. According to the monotone stack, the coordinate boundary is obtained during the operation of the stack, and the maximum area is obtained