155. Min Stack
Explanation
To achieve constant time complexity for each function, we can use an additional stack to keep track of the minimum element at each level of the main stack. Whenever we push an element onto the main stack, we also check if it is smaller than the current minimum element. If it is, we push it onto the minimum stack as well. When popping elements, we also check if the element being popped is the current minimum, in which case we pop from the minimum stack as well.
This approach allows us to retrieve the minimum element in constant time by simply peeking at the top of the minimum stack.
- Time complexity for each function: O(1)
- Space complexity: O(n)
import java.util.Stack;
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.