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.
1#include <stdio.h>
2#include <limits.h>
3#define MAX_SIZE 30000
4
5typedef struct {
6 int data[MAX_SIZE];
7 int minData[MAX_SIZE];
8 int top;
9 int minTop;
10} MinStack;
11
12MinStack* minStackCreate() {
13 MinStack* stack = (MinStack*)malloc(sizeof(MinStack));
14 stack->top = -1;
15 stack->minTop = -1;
16 return stack;
17}
18
19void minStackPush(MinStack* obj, int val) {
20 obj->data[++obj->top] = val;
21 if (obj->minTop == -1 || val <= obj->minData[obj->minTop]) {
22 obj->minData[++obj->minTop] = val;
23 }
24}
25
26void minStackPop(MinStack* obj) {
27 if (obj->top == -1) return;
28 if (obj->data[obj->top] == obj->minData[obj->minTop]) {
29 obj->minTop--;
30 }
31 obj->top--;
32}
33
34int minStackTop(MinStack* obj) {
35 return obj->data[obj->top];
36}
37
38int minStackGetMin(MinStack* obj) {
39 return obj->minData[obj->minTop];
40}
41
42void minStackFree(MinStack* obj) {
43 free(obj);
44}
45The C solution uses simple arrays to maintain the main stack and the minimum stack. We use indices to track the current position in both stacks. The main operations are very similar to basic stack operations but with an additional stack handling minimums.
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.
1import java.util.Stack;
2
3class MinStack {
4 private Stack<int[]> stack;
5
6 public MinStack() {
7 stack = new Stack<>();
8 }
9
10 public void push(int val) {
11 if (stack.isEmpty()) {
12 stack.push(new int[]{val, val});
13 } else {
14 int currentMin = Math.min(val, stack.peek()[1]);
15 stack.push(new int[]{val, currentMin});
16 }
17 }
18
19 public void pop() {
20 stack.pop();
21 }
22
23 public int top() {
24 return stack.peek()[0];
25 }
26
27 public int getMin() {
28 return stack.peek()[1];
29 }
30}
31In Java, storing each stack element as an array lets you maintain both the value and the minimum value up to that point. It allows efficient retrieval of the minimum by inspecting the pair stored at any position in the stack, primarily the top.