Recently I have been looking at data structures and algorithms, trying to sum up my debut ~

TL; DR

The characteristics of the stack: advanced after out.

Often used to solve:

  • Parenthesis validity: traversal, if the left parenthesis is on the stack, if the right parenthesis is matched, it is off the stack, otherwise false. After iterating, the stack value is false, or true
  • Next larger element problem: Iterating backwards, changing the next unknown to the previous known, maintaining decrement stacks, i.e., moving smaller than the top of the stack, or moving out of the stack
  • Minimum stack: generally “space for time”, use secondary stacks

Loop array: Using the mod technique, you don’t actually augment the array, but when iterating it feels like you’re iterating through a loop array.

Exercise: Valid parentheses

The characteristics of the stack are: last in first out

For validity, we can put the left parenthesis at the top of the stack because the left parenthesis should be closed first

If the string does not match the element at the top of the stack, the value will be false. After iterating, false if the stack has elements, and true if it has elements.

// Make it semantically explicit
const top = (stack) = > stack[stack.length - 1];

function isValid(s) {
  let stack = [];
  // the dictionary stores pairing information
  let dict = {
    "{": "}"."[": "]"."(": ")"};for (let i = 0; i < s.length; i++) {
    let cur = s[i];
    // Is the left parenthesis
    const isLeft = cur in dict;
    // open parenthesis into the stack
    if (isLeft) stack.push(cur);
    // Close parenthesis, see if it matches the top of the stack, if it does, false if it does not
    else {
      const isPair = dict[top(stack)] === cur;
      if(! isPair)return false; stack.pop(); }}// If there are elements in the stack, false, and if there are elements in the stack, true
  return! stack.length; }Copy the code

Space is O(n), time is O(n).

You can see the official solution

Exercise: Next bigger element 1

Now, the violent solution to this problem is pretty easy to imagine, is to scan the back of each element to find the first larger element. But the time of the violent solution is O(n^2).

The next, larger kind of problem can be thought of abstractly: think of the elements of an array as people standing side by side, and the size of the elements as the height of an adult. How do you find the Next Greater Number of element “2” when these people stand in a row facing you? Very simple, if you can see element “2”, then the first person visible behind him will be the Next Greater Number of “2”, because elements smaller than “2” are not tall enough and are blocked by “2”, the first person exposed is the answer.

The next big element problem: You can have the same set of ideas and templates

  • Go backwards, turning the next unknown into the previous known
  • Decrement stack is maintained, and one larger than the top of the stack is pushed off the stack until one smaller than the top of the stack or empty is pushed onto the stack
const top = (arr) = > arr[arr.length - 1];

/ /,4,6,2 [1] = > {1:4, 4:6, 6:1, 2, 1}
var _nextGreaterElement = function (arr) {
  / / decreasing stack
  let stack = [];
  // Answer storage, which varies by question
  let res = {};
  // Go backwards
  for (let i = arr.length - 1; i >= 0; i--) {
    let cur = arr[i];
    // Maintain decrement stack, when encountering something larger than the top of the stack, the stack is pushed off until encountering something smaller than the top of the stack or empty, the operation answer and current value are pushed onto the stack
    while (stack.length && cur >= top(stack)) {
      stack.pop();
    }
    // Store the answers. This varies according to the question
    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 the code

So the time is order m plus n, and the space is order m plus n.

Monotone stacks solve problems like Next Greater Number

Exercise: Next bigger element 2

This is more complicated than the last one because of the loop array.

This kind of problem, actually a little change next train of thought is good ~

[1,4,3] => loop array => [1,4,3,1,4,3]

But you don’t really have to expand the array like that, you do a little bit of a mod trick, so it’s a double, but the value of cur is arr[I %len].

And then we use the same idea, but we only need to start storing the answer at the actual length.

const top = (arr) = > arr[arr.length - 1];
var nextGreaterElements = function (nums) {
  / / decreasing stack
  let s = [];
  // This is an array
  let ans = [];
  const len = nums.length;
  // In reverse order, the array length becomes twice as long
  for (let i = len * 2 - 1; i >= 0; i--) {
    // Use mod to compute the current value. It looks like we are actually iterating through the loop array
    let cur = nums[i % len];
    while (s.length && cur >= top(s)) {
      s.pop();
    }
    // At the length of the actual array, start storing the answer
    i < len && (ans[i] = s.length ? top(s) : -1);
    s.push(cur);
  }
  return ans;
};
Copy the code

Both time and space complexity are O(n)~

Monotone stacks solve problems like Next Greater Number

Quick try: Daily temperature

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].

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();
    }
    // It depends on the case
    res[i] = s.length ? top(s) - i : 0;
    s.push(i);
  }
  return res;
};
Copy the code

Exercise: Minimum stack

The thing that’s actually a little bit more complicated here is getMin, the brute force method is definitely easy, but O(n), you want to get to O(1).

In addition to storing data, each push also maintains a minimal stack (secondary stack), the top of which is the smallest element of the current array. When pop, the top element pops out.

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 the code

Of course, this is the idea of synchronous stack, not synchronous stack, I personally feel a little complex, interested can continue to study ~

Official animation problem solving

reference

  • The front-end algorithm and data structure of xiuyan