“🌟🌟🌟🌟🌟“
“Taste: Sour and spicy lemon shrimp“
“Cooking time: 10min“
Github github.com/Geekhyt, welcome to the canteen, if you think the food is delicious, a Star is a great encouragement to the canteen owner.
Understand the Stack Stack
The bartender in the front canteen understands the stack very well. Let’s listen to how he understands the stack.
The bartender is very diligent, he does all the kitchen work at the front desk, and every day he runs back and forth to serve the dishes that customers have eaten. Stacks are like stacked plates. When the guests finish their meal happily, the waiter goes to clean up the table and picks up the plates. He puts them one by one from the bottom up. When he took the plates from the back cupboard to the cook, he took them one by one from the top down.
This is called LIFO (Last In, First Out).
In JavaScript, we can simply simulate a stack down with arrays:
function Stack() {
var items = [];
// Add elements to the top of the stack
this.push = function(element) {
items.push(element);
}
// Remove the elements at the top of the stack and return them
this.pop = function() {
return items.pop();
}
// Return the element at the top of the stack without modifying the stack
this.peek = function() {
return items[items.length - 1];
}
// Check whether the stack is empty, true if it is empty, false otherwise
this.isEmpty = function() {
return items.length === 0;
}
// Return the number of elements in the stack
this.size = function() {
return items.length;
}
/ / empty stack
this.clear = function() {
items = [];
}
}
Copy the codeThe characteristics of the stack
- A stack is an “operation-constrained” linear table in which data can only be inserted or deleted from one end.
- The time complexity and space complexity of both loading and unloading are O(1).
The application of the stack
There are many applications of stack, such as we are familiar with the function call stack, browser forward and backward as well as Hanover tower mini games.
LeetCode bo
- 84. Largest rectangle in a bar chart
Click the link above to jump to read the question, this is a difficult question, but do not be confused by it, in fact, it is not difficult.
The most intuitive way to solve this problem is brute force. We can analyze the wave first:
The first reading of the problem is essentially the largest area of a rectangle that can be drawn by n columns of width 1.
Isn’t that just kindergarten math?
Area is base times height
Lu it!
Violence law
Method 1: double loop through all the possibilities, in the process of traversal we can also find the minimum height.
const largestRectangleArea = function(heights) {
let maxArea = 0;
let len = heights.length;
for (let i = 0; i < len; i++) {
let minHeight = heights[i];
for (let j = i; j < len; j++) {
minHeight = Math.min(minHeight, heights[j]);
maxArea = Math.max(maxArea, minHeight * (j - i + 1));
}
}
}
Copy the codeMethod two: after determining a column, traverse it in two directions, respectively.
const largestRectangleArea = function(heights) {
let maxArea = 0;
let len = heights.length;
for (let i = 0; i < len; i++) {
let left = i;
let right = i;
while (left >= 0 && heights[left] >= heights[i]) {
left--;
}
while (right < len && heights[right] >= heights[i]) {
right++;
}
maxArea = Math.max(maxArea, (right - left - 1) * heights[i]);
}
return maxArea;
}
Copy the codeBut both methods are O(n^2) in time and O(1) in space. The time complexity is too high and we need to find ways to optimize it.
Use monotonically increasing stacks
So let's think about the question, what is the maximum area that we want?
Might as well pick up the pen to draw a picture, I help you draw, observe the above picture, you can get:
In fact, by highlighting the I, the first two boundaries smaller than heighs[I] are highlighted left and right, respectively, as the largest area outlined by the current I column.
So why do we resort to data structures like monotonically increasing stacks?
Monotonically increasing, that is, we can determine the left boundary of cylinder I by the time complexity of O(1)!
Another space for time routine!
How do I determine the right boundary?
We simply iterate through the array of columns once, pushing the columns that are greater than or equal to the current column onto the stack. When the height of the column traversed is less than the height of the top column, we find the right boundary and can pop the top column off the stack to calculate the area of the rectangle!
Dealing with special boundary cases?
Introduce front and back boundaries, and place a column of height 0 before and after the column array. This eliminates the need to worry about empty stacks and remaining columns in the stack!
Ok, code!
const largestRectangleArea = function(heights) {
let maxArea = 0;
let stack = [];
heights.push(0);
heights.unshift(0);
// heights = [0, ...heights, 0]; You could also write it like this
for (let i = 0; i < heights.length; i++) {
while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack[stack.length - 1] - 1));
}
stack.push(i);
}
return maxArea;
}
Copy the code- Time complexity: O(N)
- Space complexity: O(N)
Hopefully this article has given you a better understanding of stacks, and if you haven’t already, you can follow my series of other algorithms.
- How the front end handles data structures and Algorithms (Pilot)
- Time and space complexity analysis of JavaScript algorithm
- Do you really understand recursion?
- Divide and conquer, dynamic programming, backtracking, greed
- The tree industry has a specialty
- Binary search algorithms from drinking table games
- Interview lists are no longer scary
❤️ Love triple punch
1. If you think the food and drinks in the canteen are ok with you, please give me a thumbs-up. Your thumbs-up is my biggest motivation.
2. Pay attention to the front canteen of public account, “eat every meal!”
3. This article has been included in the front canteen Githubgithub.com/GeekhytHope to get your little star encouragement.
