This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Minimum stack (Question No. 155)

The title

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

  • push(x)– the elementxPush it on the stack.
  • pop()Delete the top element of the stack.
  • top()Get the top element on the stack.
  • getMin()Retrieve the smallest element in the stack.

Example:

Input:"MinStack"."push"."push"."push"."getMin"."pop"."top"."getMin"[[]], [...2], [0], [...3[],[],[],[],[]null.null.null.null, -3.null.0, -2[Explanation: MinStack MinStack =new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3); minStack.getMin(); -- -- > returns3.minStack.pop(); minStack.top(); - > to return0.minStack.getMin(); -- -- > returns2.
Copy the code

Tip:

  • pop,top 和 getMinThe operation is always onStack is not emptyOn the call.

link

Leetcode-cn.com/problems/mi…

explain

This one. This one is Jane and I failed.

The interview was asked, the result did not answer to come out ~

If the normal brush the question is no problem ah, the results of the interview do not know whether because of too nervous, a little train of thought, and finally in the interviewer’s reminder to answer out.

It was O(n) time to think about it, and O(1) was impossible to think about.

O(n) is actually easy to operate, just use math.min and just take the minimum value, there’s nothing to say about it.

O(1), you have to think about the timing of the smallest element.

If we want getMin to be O(1), then we need to prove that we need to get the minimum number at either push or pop. If we want getMin to be O(1), we need to prove that we need to get the minimum number at either push or pop. Order n time again.

In fact, the root of this problem lies in the push operation, and it is very simple to do. Record the current minimum number for each push, and compare the current value with the minimum value of the last push in the next push, and then record the minimum value of the current position.

The pop operation simply pulls out the last element of the array. There is no additional operation. All you need to do is maintain a variable, which can be an array or an object, by fetching the minimum value of the previous length and then updating the minimum value of the current length.

It’s really very simple to understand, but I didn’t think of it at that time, alas ~

Your own answer

var MinStack = function() {
  this.x_stack = [];
  this.min_stack = [Infinity];
};

MinStack.prototype.push = function(x) {
  this.x_stack.push(x);
  this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));
};

MinStack.prototype.pop = function() {
  this.x_stack.pop();
  this.min_stack.pop();
};

MinStack.prototype.top = function() {
  return this.x_stack[this.x_stack.length - 1];
};

MinStack.prototype.getMin = function() {
  return this.min_stack[this.min_stack.length - 1];
};
Copy the code

The whole idea is that we need to maintain an array inside the MinStack to record the minimum value of the current position. When we push, we push a new element into the min_stack. This element is the last element in the MIN_stack and the minimum value of the current inserted value. To pop, remove the last element of x_stack and the last element of min_stack, so that the last element of min_stack is always the latest and smallest; Top just takes the last element of x_stack; GetMin takes the last element in the min_stack.

Typical space for time, it’s a shame I didn’t think of it

A better way

There is no




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)