## When encountering bracket validity, next larger element, specific minimum value, try stack

Yanjiang 2021-04-07 21:46:53
encountering bracket validity larger element

Recently I've been looking at data structures and algorithms , Try to sum up ~

## TL;DR

The characteristics of the stack ： First in, then out .

Often used to solve ：

• Bracket validity ： Traverse , In case of left bracket, put it on the stack , Right parenthesis encountered , Matching is out of the stack , otherwise false. End of traversal , The stack value is false, Instead of true
• The next big element series ： Traverse backwards , Change the next unknown into the last known , Maintain the decrement stack , It's smaller than the top of the stack , Otherwise, it will be out of the stack
• Smallest stack ： commonly “ Space for time ”, Use the auxiliary stack

Circular array ： Using the technique of redundancy , There is no actual expansion array , But when traversing , It's like traversing a circular array .

## practice ： Valid brackets

The characteristic of a stack is ： Last in, first out

For effectiveness , Because the left bracket encountered after must be closed first , So we can put the left bracket at the top of the stack , You can get out of the stack when you meet the right bracket , The feeling of Xiaole ~

Ideas ： Traversal string , When I encounter the left bracket, I put it on the stack , Right parenthesis encountered , It doesn't match the elements at the top of the stack `false`, If it matches, it's out of the stack . After traversing , If the stack has elements , explain `false`, Instead of `true`.

``````// It's more semantic
const top = (stack) => stack[stack.length - 1];
function isValid(s) {
let stack = [];
// Dictionaries store pairing information
let dict = {
"{": "}",
"[": "]",
"(": ")",
};
for (let i = 0; i < s.length; i++) {
let cur = s[i];
// Is it the left bracket
const isLeft = cur in dict;
// Left bracket in stack
if (isLeft) stack.push(cur);
// Right bracket , Check with the top of the stack , Yes, it's out of the stack , Not so false
else {
const isPair = dict[top(stack)] === cur;
if (!isPair) return false;
stack.pop();
}
}
// End of traversal , If there are elements in the stack, they are false, Conversely true
return !stack.length;
}
Copy code ``````

Space is O(n), Time, too O(n)

May have a look Official explanation

## practice ： Next bigger element 1

The violent solution to this problem is very good , It's just scanning the back of each element , Just find the first larger element . But the time complexity of the brute force solution is O(n^2).

The next bigger problem of this kind You can think abstractly like this ： Think of the elements of an array as people standing side by side , Element size imagine the height of an adult . These people stand in a line in front of you , How to find elements 「2」 Of Next Greater Number Well ？ It's simple , If you can see the elements 「2」, So the first person behind him is 「2」 Of Next Greater Number, Because than 「2」 Small elements are not tall enough , All be 「2」 It's in the way , The first thing that comes out is the answer .

The next big element series ： You can use the same set of ideas and templates

• Traverse backwards , Change the next unknown into the last known
• Maintain the decrement stack , Meet someone bigger than the top of the stack , The top of the stack , Until you meet someone smaller than the top of the stack or the stack is empty , Push
``````const top = (arr) => arr[arr.length - 1];
// [1,4,6,2] => {1:4,4:6,6:-1,2:-1}
var _nextGreaterElement = function (arr) {
// Decrement stack
let stack = [];
// Answer storage , It depends on the topic
let res = {};
// Traverse backwards
for (let i = arr.length - 1; i >= 0; i--) {
let cur = arr[i];
// Maintain the decrement stack , Meet someone bigger than the top of the stack , The top of the stack , Until you meet someone smaller than the top of the stack or the stack is empty , Put the answer and current value on the stack
while (stack.length && cur >= top(stack)) {
stack.pop();
}
// Store answers , It depends on the topic
res[i] = stack.length ? top(stack) : -1;
stack.push(cur);
}
return res;
};
var nextGreaterElement = function (nums1, nums2) {
const res = _nextGreaterElement(nums2);
return nums1.map((item) => res[item]);
};
Copy code ``````

So the time complexity is O(m+n), The complexity of space is also O(m+n)

Monotonous stack solution Next Greater Number A class of questions

## practice ： Next bigger element 2

This question is more complicated than the one just now , On the loop array .

This kind of problem , In fact, a little change in thinking is good ~

[1,4,3] => In the case of circular arrays => [1,4,3,1,4,3]

But you don't really need to expand arrays like this , Use the little technique of surplus collection , The number of iterations is twice the number of arrays , however cur The value is `arr[i%len]`

And still use the above ideas , however , To store answers here, you just need to start at the actual length .

``````const top = (arr) => arr[arr.length - 1];
var nextGreaterElements = function (nums) {
// Decrement stack
let s = [];
// It is stored here according to the topic , This problem can be solved by array
let ans = [];
const len = nums.length;
// Reverse traversal , The length of the array becomes 2 It's twice as long
for (let i = len * 2 - 1; i >= 0; i--) {
// Calculate the current value with the remainder operation , On the surface, it looks like it's actually traversing a circular array
let cur = nums[i % len];
while (s.length && cur >= top(s)) {
s.pop();
}
// At the length of the actual array , Start storing answers
i < len && (ans[i] = s.length ? top(s) : -1);
s.push(cur);
}
return ans;
};
Copy code ``````

Time complexity and space complexity are both O(n)~

Monotonous stack solution Next Greater Number A class of questions

Give it a quick try : Daily temperature

Please according to the daily The temperature list , Rebuild a list . The output of the corresponding position is ： To see a higher temperature , At least the number of days to wait . If the temperature doesn't rise after that , Please use... In this position  0 Instead of .

for example , Given a list  temperatures = [73, 74, 75, 71, 69, 72, 76, 73], Your output should be  [1, 1, 4, 2, 1, 1, 0, 0].

``````const top = (arr) => arr[arr.length - 1];
var dailyTemperatures = function (T) {
let s = [];
let res = [];
for (let i = T.length - 1; i >= 0; i--) {
const cur = T[i];
while (s.length && cur >= T[top(s)]) {
s.pop();
}
// As the case may be , The number of days is calculated here , Obviously, storage i appropriate
res[i] = s.length ? top(s) - i : 0;
s.push(i);
}
return res;
};
Copy code ``````

## practice ： Smallest stack

A little bit of trouble here is ,getMin, The violence law must be easy , But time complexity O(n), Want to be O(1).

Another way of thinking , Every time push When , In addition to storing data , And maintain the minimum stack ( Auxiliary stack ), The top of the stack is the smallest element of the current array ;pop When , Top of stack element pop up .

``````function Stack(){
this.data = []
this.helpStack = []
}
Stack.prototype.push = num => {
this.data.push(num)
this.helpStack.push(num<this.data[this.data.length-1]?num:this.data[this.data.length-1])
}
Stack.prototype.pop = () => {
this.data.length && this.data.pop()
this.helpStack.length &&this.helpStack.pop()
}
Stack.prototype.getMin = () => {
return this.helpStack[this.helpStack.length-1]
}
Copy code ``````

Of course, this is the idea of synchronization stack , Different steps , Personally, I think it's a little complicated , Those who are interested can continue to study ~

Official animation

## quote

https://qdmana.com/2021/04/20210407213623127q.html