Previously we learned a lot about stack knowledge, such as “GIF Demo: Two Ways to Implement handlift Stack!” “And” How does the JDK implement stacks?” So let’s brush up on some classic stack interview questions to reinforce what we’ve learned.
Here’s our interview question for today…
The title
Define the data structure of the stack. Please implement a min function in this type that can get the smallest element of the stack. In this stack, the time complexity of calling min, push and pop is O(1).
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); — — > to return to 3.
minStack.pop();
minStack.top(); — > 0 is returned.
minStack.min(); — — > to return to 2.
LeetCode address: leetcode-cn.com/problems/ba…
thinking
First of all, the problem itself is very easy to understand, its implementation difficulties lie in the following two aspects:
- If we remove the current minimum when we pop, how do we find the next minimum?
- Make sure the time complexity of the calls min, push, and POP is O(1).
That is, if we remove the smallest value in the stack when we perform pop, how do we find the next smallest element in the stack? Ensure that the operation time complexity is O(1). This time complexity restricts us from traversing to find the next minimum after removing the minimum, so this becomes the difficulty of this problem.
For example, if we remove the following top of the stack:
Their thinking
In fact, we can determine whether the current element is less than the minimum value each time we push it, if it is less than the original minimum value and the latest minimum value will be pushed successively, so that when we call POP, even if the minimum value is removed, we can get a new minimum value by fetching the next element, as shown in the following process.
Procedure 1
The first element is pushed, and since it is the first element, the minimum value is the value of that element.
Procedure 2
The second element is pushed as shown below:
Procedure 3
The third element is pushed, as shown below:
Step 4
Continue pushing, as shown below:
Step 5
Perform the unstack operation, as shown below:
Step 6
Continue to unstack, as shown below:
Step 7
Continue to unstack, as shown below:
Implementation Code 1
Next we will use the above ideas to achieve the code, we use the array stack to achieve the relevant functions, the code is as follows:
class MinStack {
private int[] data; / / stack data
private int maxSize; // Maximum length
private int top; // top pointer (subscript)
private int min; / / the minimum
// constructor
public MinStack(a) {
// Set the default value
maxSize = 10000;
data = new int[maxSize];
top = -1;
min = Integer.MAX_VALUE;
}
// Push (add element)
public void push(int x) {
if (min >= x) {
// A smaller value is encountered, record the original minimum value (push)
data[++top] = min;
min = x;
}
// The current value is pushed
data[++top] = x;
}
// remove top element from stack
public void pop(a) {
if (min == data[top]) {
min = data[--top]; // Get the original minimum and push it off the stack
}
--top; / / out of the stack
}
// Find the top element on the stack
public int top(a) {
return data[top];
}
// Query the minimum value
public int min(a) {
returnmin; }}Copy the codeThe above code is executed in LeetCode as follows:
You can see that the performance is still very high, exceeding 99.92% of users, and the memory consumption is not very high. Its core code in the push method, first the original minimum value and the latest minimum value into the stack one after another, when pop out of the stack to judge whether the stack element is the minimum value, if the minimum value is the current minimum value to the top of the stack element and the top of the stack element out of the stack, so as to get the next new minimum value.
Implementation Code 2
If we don’t want to use a custom Stack of arrays, we can also use Java’s own Stack Stack to implement this functionality, as follows:
class MinStack {
private Stack<Integer> stack = new Stack<>();
private int min = Integer.MAX_VALUE;
public MinStack(a) {}// Push (add element)
public void push(int x) {
if (x <= min) {
// A smaller value is encountered, record the original minimum value (push)
stack.push(min);
min = x;
}
stack.push(x);
}
// remove top element from stack
public void pop(a) {
if (stack.pop() == min) {
min = stack.pop(); // Get the original minimum value}}// Find the top element on the stack
public int top(a) {
return stack.peek();
}
// Query the minimum value
public int min(a) {
returnmin; }}Copy the codeThe above code is executed in LeetCode as follows:
As you can see, using the native stack in Java doesn’t perform as well as using the custom array stack, but the code still passes the test. The advantage of this implementation is that the code is relatively simple, and the Java API can be used to complete the minimum value search.
This way of implementing the code (using the Java API) can be used in a brush test or actual interview without special instructions.
conclusion
In this paper, we implement the function of the minimum value in the Stack in two ways: the custom array Stack and the Stack in the Java API to ensure that the time complexity of calling the min, push and POP methods of the Stack is O(1). The code of the two implementations is slightly different, but the implementation idea is the same, both of which determine whether the current element is smaller than the minimum element when the element is pushed, if it is smaller than the minimum element, the original minimum value is pushed first, then the current minimum element is pushed, so that when the pop method is called, even if the minimum value is removed, Just pull out the next element to be the new minimum, so that the time complexity for calling min, push, and POP methods is O(1).
The last
Let me know in the comments section
Original not easy, everybody quality four couplet, thank.
Bonus: search the public account “Java Chinese Community” and send “interview” to receive the latest interview materials.