Hello everyone, today I would like to share with you the next LeetCode difficult difficulty problem [the largest rectangle in the bar chart].

The title

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

The opening parenthesis must be closed with a closing parenthesis of the same type. The opening brackets must be closed in the correct order. (Image of leetCode)

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

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

Analysis of the

1. Column height can be repeated

2. Area is the column spacing * the minimum height of the column

2. Return maximum area

solution

1. Stack +array *1

Solution 1: Stack +array

Thinking from leetcode-cn.com/problems/la…

Train of thought1.Iterate the height of each column to find the area2.When height is sometimes the maximum width is required,3.In order to find the maximum width, you must find the left boundary and the right boundary which are lower than its height4.Use the stack mechanism1.The lowest level of the stack must be the lowest height of the accessed elements,2.If the new column is taller than the previous column, push the new element into the stack3.When the pole at the top of the stack is smaller than the pole at the top of the stack, the right boundary has been found, and the area of the column stored in the stack can be started4.Remove the calculated column pop, still keeping the lowest level of stack as the smallest height ever accessed5.Start to continue the loop step2
    6.When iterating through the entire array, you need to clear the stack and calculate the area5.Set the left and right boundaries for each topic6.Final statistics */var largestRectangleArea = function (heights) {
  // The index used to hold the element
  const stack = [];
  // Index for the left edge of all columns
  let left = [];
  // Index for the right edge of all columns
  let right = new Array(heights.length);
  right.fill(heights.length);
  let max = 0;

  for (let i = 0; i < heights.length; i++) {
    // If the stack has a value and the new element is greater than the top element of the stack, replace the right edge of those elements in the stack
    while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
      right[stack[stack.length - 1]] = i;
      stack.pop();
    }
    // If the stack has no value, the value is -1. If it has a value, the boundary is changed to the last value in the stack
    left[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    // Put the index of the current element in the stack
    stack.push(i);
  }

  // Statistics
  for (let i = 0; i < heights.length; i++) {
    max = Math.max(heights[i] * (right[i] - left[i] - 1), max);
  }

  return max;
};

/* Complexity time O(n) space O(n) */
Copy the code

Solution 2: Violence (timeout)

Train of thought1.Iterate over each column to find the maximum area available for the current column2.Find the boundary left and find the boundary right */var largestRectangleArea = function (heights) {
  let max = 0;

  for (let i = 0; i < heights.length; i++) {
    const height = heights[i];
    let left = i;
    let right = i;

    // Find the boundary to the left
    while (left > -1) {
      const leftHeight = heights[left];
      if (leftHeight < height) {
        break;
      } else{ left--; }}/* Look right for the boundary */
    while (right < heights.length) {
      const rightHeight = heights[right];
      if (rightHeight < height) {
        break;
      } else{ right++; }}// Update the minimum area
    max = Math.max(max, height * (right - left - 1));
  }

  return max;
};
/* Complexity time O(n^2) space O(1) */
Copy the code

conclusion

It’s a little hard to understand, but the whole point is to use the stack to store the leftmost boundary and prevent repeated searches, because in brute force there’s a lot of repetition of left searches

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]