This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

63. Various temperatures are caused by daily temperatures.

The label

  • Monotonous stack
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Generate a new list based on the daily temperature list. The output of the corresponding position is: the minimum number of days to wait for higher temperatures to be observed. If the temperature does not rise after that point, substitute 0 at that point.

For example, given a list of temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output would be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length range of the temperature list is [1, 30000]. Each temperature is an integer in the [30, 100] range of degrees Fahrenheit.

The relevant knowledge

The typical NGE (Next Greater Element) question is not asking you what the Next Greater Number is, but the current distance to the Next Greater Number.

Monotone stacks were explained and exemplified in the previous article, but if you don’t know, move on to monotone stacks

Basic steps

We still maintain a monotonic stack of subscripts according to the monotonic stack principle, (we still set a stack to place index index), from the bottom of the stack to the top of the subscript corresponding to the temperature list in descending order. If a subscript is in the monotone stack, the next higher temperature subscript has not been found.

  1. Forward traversal of the temperature list.
  2. For each element in the temperature listT[i].
    • If the stack is empty, I is just pushed onto the stack,
    • Compares if the stack is not emptyThe stack elements prevIndexCorresponding temperatureT[prevIndex] andThe current temperature T[i].
      • ifT[i] > T[prevIndex], it willprevIndex removeAnd willprevIndexThe corresponding waiting days are assigned toi - prevIndexRepeat the preceding operationsUntil the stack is emptyorThe temperature of the element at the top of the stack is less than or equal to the current temperatureAnd thenWill I into the stack.

Why is it possible to update res[prevIndex] on reload? Because in this case, T[I] of the I to be pushed must be the first element to the right of T[prevIndex]. Imagine if prevIndex and I have elements larger than it, assuming subscript j, then prevIndex must be popped in the j round.

Since the monotone stack satisfies the temperature decreasing from the bottom of the stack to the top of the stack, every time an element is added to the stack, the element with lower temperature will be removed and the corresponding waiting days of the element out of the stack will be updated, which ensures that the waiting days must be minimum.

Writing implement

var dailyTemperatures = function(T) {
  let [stack, res] = [[], new Array(T.length).fill(0)]
  for (let i = 0; i < T.length; i++) {
    while (stack.length && T[i] > T[stack[stack.length - 1]]) {
      PrevIndex = prevIndex; prevIndex = prevIndex; prevIndex = prevIndex
      let prevIndex = stack[stack.length - 1]
      / / out of the stack
      stack.pop()
      // Find the distance in the array
      res[prevIndex] = i - prevIndex
    }
    // Push current index to the top of the stack
    stack.push(i)
  }
  return res
};

console.log(dailyTemperatures([55.38.53.81.61.93.97.32.43.78]))
Copy the code

65. Largest rectangle in the histogram (largest- Rectangle -in-histogram)

The label

  • Monotonous stack
  • difficult

The title

Leetcode portal

Let’s just open leetCode.

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.

The above is an example of a bar chart, where each column is 1 in width and the given height is [2,1,5,6,2,3].

 

The shaded part of the figure is the largest rectangular area that can be outlined, and its area is 10 units.

Example:

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

The relevant knowledge

Monotone stacks were explained and exemplified in the previous article, but if you don’t know, move on to monotone stacks

The basic idea

This idea comes from other people’s problem solving, which I think is very clear. Here is the original text

A noun meaning

  • Tall camp: Examine the histogram from left to right. There are already rectangles before the next bar. The taller camp is the tall camp.
  • Short camp: The opposite of the tall camp

Each camp has its advantages

  • When you encounter a new bar
    • The tall camp is not compatible with it, but also because of the “barrier” of the low bar, the area has stopped growing since then
    • Shorter factions can accommodate it, thus increasing length and area
    • The short camp is short, but compatible, and becomes stronger by getting longer
    • Tall camp is high, but compatibility is poor, meet high is strong, meet low is stagnant growth

The different meanings brought by high bar and short bar

  • With a high bar, both factions can boost. Now we don’t have to calculate the area, because the area is getting bigger, not the maximum
  • There comes a short bar, the area of the tall camp can not be larger, the short camp has the possibility of counterattack. It is meaningless to investigate the tall camp. After calculating the area, you can discard it and continue to observe the short camp

Here’s the thing. Height is relative

  • There is no absolute high bar, there is no absolute short bar, there is no absolute tall camp, there is no absolute short camp
  • Do we have to distinguish between tall and low camps based on a new bar every time? Obviously not practical

Height is created by comparison

  • Take for example: Xiao Wang, the military training assembly is late
  • If the teams are uneven at this point, it is difficult to tell who is taller and who is shorter than Xiao Wang
  • If the line is arranged according to the height and Wang compares them one by one from the head of the line, it is easy for everyone to know who is taller
  • It’s easy for Wang to know where to line up, right

Make the comparison process faster

  • Arrange the height and height (maintain a monotonic sequence) to welcome the arrival of the new bar
  • So the question is, do you maintain a monotonous stack or a monotonous queue? Monotonically increasing or monotonically decreasing?

Why is it monotonically increasing? Why stack?

  • If it’s a monotone decreasing stack
    • The new BAR is shorter than the top of the stack, and is pushed into the stack to maintain the diminishing property
    • The new bar is higher than the top of the stack, the short camp near the top of the stack will strengthen, continue to investigate, the tall row behind stop growing, need to be abandoned
    • But the tall camp is not on the top of the stack, it is not easy to get out of the stack
  • So, is the queue ok? Let the tall man fall off the back of the line?
    • Ok, but if a new bar comes in, it needs to enter the column from the high place to maintain monotonicity. This is not a queue, but a stack
  • So, it has to beMonotonically increasing stack
    • The new BAR is higher than the top of the stack
    • The new BAR is lower than the top of the stack, and the tall camp at the top of the stack stops growing and exits the stack, while the short camp at the back is left for observation

The monotonicity of the stack, who goes and who stays, becomes clear

  • The tall lineup meets the high bar and stops developing, calculates the rectangular area it forms, and then leaves the stack
  • The stack is monotonically increasing, constantly comparing the top bar of the new stack with the current bar, and the higher bar goes
  • When the top bar of the stack is no longer higher than the current bar, the current bar is no longer removed from the stack and pushed onto the current bar

What does the monotone stack record?

  • Position of bar (index),
    • throughheight[i]calculate
    • The width is found by subtracting the index

Basic steps

  • Maintain a stack. Iterate over each bar in the Heights array
  • The current bar is higher than the bar at the top of the stack
  • Current bar is shorter than the bar at the top of the stack:
    • The top element (index) goes off the stack and is temporarily stored tostackTopIndexvariable
    • To computeheights[stackTopIndex]Is the area of the tall rectangle, width = current bar index I – new top stack index -1, compared with the global maximum
  • The current bar continues to be compared with the new top of the stack, and the above process is repeated until the current bar is no longer shorter than the bar at the top of the stack

The following is an analysis of the boundary case

If the stack is empty, the area formula won’t work

  • To find the width of a rectangle, you need a new top of the stack. When the stack has only one element, the stack is pushed out of the stack, and the stack is empty
  • Let’s consider another question: what is the basis for pushing index 0 of the Heights array?
  • The basis for pushing is that the current bar is higher than the top bar. The problem is that there is no top of the stack to compare
  • We canSet up a virtual bar with height 0, placed at 0 in the heights, it does not affect the result, but allows the index of the first bar to be properly pushed
  • It also solves the first problem: no other bar can be shorter, so the bar is never out of the stack

The last bar needs rescuing

  • The last bar will not encounter the new bar, if it is in the stack, there is no chance to exit the stack, meaning, there is no chance to calculate the area of the rectangle in the stack
  • We set up a virtual bar with a height of 0 and put it at the far right of the heights array. All the bars in the stack are higher than it. We can exit the stack one by one and get the rescue

Writing implement

var largestRectangleArea = function(heights) {
  if(! heights || ! heights.length) {return 0;
  }
  // Add 0 to both ends to handle the termination condition of the while
  heights.unshift(0)
  heights.push(0)
  // Get the pure function of the top element on the stack
  const stackTopItem = () = > stack[stack.length - 1]
  let [maxArea, stack] = [0, [the]]for (let i = 0; i < heights.length; i++) {
      // The stack has a value and the current bar is shorter than the top bar
      while (stack.length && heights[stackTopItem()] > heights[i]) {
        // The top element is removed from the stack, and the index of the top bar is saved
        const stackTopIndex = stack.pop() 
        // Get the maximum width of the term closest to the left
        const width = i - stackTopItem() - 1 
        // Calculate the area, take the maximum value
        maxArea = Math.max(maxArea, width * heights[stackTopIndex] )
      }
      // The current bar is higher than the top bar of the stack
      stack.push(i)
    }
    return maxArea
};

console.log(largestRectangleArea([2.1.5.6.2.3]))
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference

  • Leetcode-cn.com/problems/da…
  • Leetcode-cn.com/problems/la…