This approach utilizes two stacks. One stack will hold the main elements, while the other stack will keep track of the minimum elements. When you push a value, it's added to the main stack, and if it's less than or equal to the current minimum, it's also pushed onto the min stack. During a pop operation, if the value being popped is the current minimum, it's also popped from the min stack.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), where n is the number of elements in the stack.
1using System.Collections.Generic;
2
3public class MinStack {
4 private Stack<int> stack;
5 private Stack<int> minStack;
6
7 public MinStack() {
8 stack = new Stack<int>();
9 minStack = new Stack<int>();
10 }
11
12 public void Push(int val) {
13 stack.Push(val);
14 if (minStack.Count == 0 || val <= minStack.Peek())
15 minStack.Push(val);
16 }
17
18 public void Pop() {
19 if (stack.Peek() == minStack.Peek())
20 minStack.Pop();
21 stack.Pop();
22 }
23
24 public int Top() {
25 return stack.Peek();
26 }
27
28 public int GetMin() {
29 return minStack.Peek();
30 }
31}
32The C# solution utilizes two Stack objects from the .NET collections, similar to other language solutions. The minStack keeps track of the smallest values. Only when pushing and popping elements that match the top of minStack are changes made to minStack.
This approach reduces space usage by storing a pair (value, minimum so far) in a single stack. Each element maintains the current minimum alongside its actual value, providing quick minimum retrieval by just examining the top of the stack.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), each element only holds a pair so space is efficient relative to the number of elements.
1#include <stack>
2#include <climits>
3class MinStack {
4 std::stack<std::pair<int, int>> stack;
5public:
6 MinStack() {}
7
8 void push(int val) {
9 if (stack.empty())
10 stack.emplace(val, val);
11 else
12 stack.emplace(val, std::min(val, stack.top().second));
13 }
14
15 void pop() {
16 stack.pop();
17 }
18
19 int top() {
20 return stack.top().first;
21 }
22
23 int getMin() {
24 return stack.top().second;
25 }
26};
27In C++, the standard stack is used, but each element is stored as a pair. The pair consists of the value and the minimum value at that time. This ensures that when popping, the integrity of the minimum remains intact because each element 'remembers' what the minimum was.