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.
- Forward traversal of the temperature list.
- For each element in the temperature list
T[i]
.- If the stack is empty, I is just pushed onto the stack,
- Compares if the stack is not emptyThe stack elements
prevIndex
Corresponding temperatureT[prevIndex]
andThe current temperatureT[i]
.- if
T[i] > T[prevIndex]
, it willprevIndex
removeAnd willprevIndex
The corresponding waiting days are assigned toi - prevIndex
Repeat 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
.
- if
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),
- through
height[i]
calculate - The width is found by subtracting the index
- through
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 to
stackTopIndex
variable - To compute
heights[stackTopIndex]
Is the area of the tall rectangle, width = current bar index I – new top stack index -1, compared with the global maximum
- The top element (index) goes off the stack and is temporarily stored to
- 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 can
Set 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…