preface

Originally thought of today’s problem solving to write today’s daily problem 131. Division palindrome string, but I do not have a special understanding, so I did not write, with the digging gold brush problem punch card activity group of today’s recommended questions to write 😄😄

Topic describes

Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.

  • Push (x) – Pushes element X onto the stack.
  • Pop () — Removes the top element of the stack.
  • Top () — Gets the top element on the stack.
  • GetMin () — Retrieves the smallest element in the stack.

Example:

Input: [" MinStack ", "push" and "push" and "push" and "getMin", "pop", "top", "getMin"] [[], [2], [0], [3], [], [], [], []] output: [null,null,null,null,-3, NULL,0,-2] MinStack MinStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> return -3.minstack.pop (); minStack.top(); --> return 0. Minstack.getmin (); -- -- > to return to 2.Copy the code

Tip:

  • Pop, top, and getMin operations are always called on a non-empty stack.

Their thinking

Push, pop, array, array, array, array, array, array, push, pop, array Use the array stack to describe a stack.

For the push and pop methods, we can directly use the array push and pop, but we need to note that we need to retrieve the smallest element, so we need to take this into account. Min_val is the smallest element, and the initial value is set to positive infinity.

The push element x and min_val are compared, and min_val takes the minimum value of both.

Pop updates the value of min_val by checking whether the last element of the array is equal to min_val.

When you’re at top, you just take the last element of the array.

Return min_val for getMin.

The problem solving code

/**
 * initialize your data structure here.
 */
 var MinStack = function() {
  this.stack = []
  this.min_val = Infinity
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  if (x <= this.min_val) {
    this.stack.push(this.min_val)
    this.min_val = x
  }
  this.stack.push(x)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  if (this.stack[this.stack.length - 1] === this.min_val) {
    this.stack.pop()
    this.min_val = this.stack[this.stack.length - 1]
    this.stack.pop()
  } else {
    this.stack.pop()
  }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.min_val
};
Copy the code

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

conclusion

It is necessary to write more questions, do not be afraid to write bad, the process of writing is the process of review, it is easier to deepen their understanding.

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign