題目

定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的 min 函數，輸入操作時保證 pop、top 和 min 函數操作時，棧中一定有元素。

此棧包含的方法有：

• push(value)：將 value 壓入棧中
• pop()：彈出棧頂元素
• top()：獲取棧頂元素
• min()：獲取棧中最小元素

數據范圍：

• 操作數量滿足 $0\le n\le 300$
• 輸入的元素滿足 $|val|\le 10000$
• 進階：棧的各個操作的時間復雜度是 $O(1)$，空間復雜度是 $O(n)$

示例

輸入：

["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

輸出：

-1, 2, 1, -1

解析：

• "PSH-1"表示將-1壓入棧中，棧中元素為-1
• "PSH2"表示將2壓入棧中，棧中元素為2, -1
• "MIN"表示獲取此時棧中最小元素==>返回-1
• "TOP"表示獲取棧頂元素==>返回2
• "POP"表示彈出棧頂元素，彈出2，棧中元素為-1
• "PSH1"表示將1壓入棧中，棧中元素為1, -1
• "TOP"表示獲取棧頂元素==>返回1
• "MIN"表示獲取此時棧中最小元素==>返回-1

---

C語言代碼實現

#define MAX_SIZE 300  // 假設棧最大容量
int stack[MAX_SIZE]; // 定義一個整數數組作為棧的存儲空間
int count = -1;      // 用于記錄棧中元素的數量// 壓入棧中的值
void push(int value) {if (count < MAX_SIZE - 1) {stack[++count] = value;} else {printf("Stack is full.\n");return;}
}// 彈出棧頂元素
void pop() {if (count == -1) {printf("Stack is empty.\n");return;}count--;
}// 獲取棧頂元素
int top() {if (count == -1) {return -1;}return stack[count];  // 返回棧頂元素的值
}// 獲取棧中最小的元素
int min() {if (count == -1) {return -1;}int minVal = stack[0]; for (int i = 1; i <= count; i++) {minVal = (minVal > stack[i]) ? stack[i] : minVal;}return minVal;
}

解釋

1. push(value)

該函數負責將一個元素壓入棧中。當棧未滿時，將元素存入 stack 數組，并將棧頂指針 count 增加。

2. pop()

該函數負責彈出棧頂元素。當棧不為空時，棧頂元素被移除，棧頂指針 count 減少。

3. top()

該函數返回棧頂的元素。如果棧為空，返回 -1，否則返回棧頂的值。

4. min()

該函數遍歷整個棧，找到最小的元素并返回。如果棧為空，返回 -1。

---

總結

這題整體上還是很簡單的，本以為是用大小堆實現的，沒想到直接一個遍歷就搞完了。明天研究一下如何用大小堆實現。

大小堆

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 300  // 假設棧最大容量// 定義堆的結構體
typedef struct {int data[MAX_SIZE];int size;  // 堆中的元素數量
} MinHeap;// 定義棧的結構體
typedef struct {int stack[MAX_SIZE];int top;MinHeap minHeap;
} Stack;// 堆的操作：插入元素
void insertMinHeap(MinHeap* heap, int value) {int i = heap->size++;heap->data[i] = value;// 維護堆的性質，逐步上浮while (i > 0 && heap->data[i] < heap->data[(i - 1) / 2]) {int temp = heap->data[i];heap->data[i] = heap->data[(i - 1) / 2];heap->data[(i - 1) / 2] = temp;i = (i - 1) / 2;}
}// 堆的操作：刪除堆頂元素
void removeMinHeap(MinHeap* heap) {if (heap->size == 0) return;heap->data[0] = heap->data[--heap->size];// 維護堆的性質，逐步下沉int i = 0;while (2 * i + 1 < heap->size) {int left = 2 * i + 1;int right = 2 * i + 2;int smallest = i;if (left < heap->size && heap->data[left] < heap->data[smallest]) {smallest = left;}if (right < heap->size && heap->data[right] < heap->data[smallest]) {smallest = right;}if (smallest == i) break;int temp = heap->data[i];heap->data[i] = heap->data[smallest];heap->data[smallest] = temp;i = smallest;}
}// 堆的操作：獲取堆頂元素
int getMin(MinHeap* heap) {return heap->size > 0 ? heap->data[0] : -1;
}// 初始化棧
void initStack(Stack* stack) {stack->top = -1;stack->minHeap.size = 0;
}// 壓棧操作
void push(Stack* stack, int value) {if (stack->top < MAX_SIZE - 1) {stack->stack[++stack->top] = value;insertMinHeap(&stack->minHeap, value);} else {printf("Stack is full.\n");}
}// 彈棧操作
void pop(Stack* stack) {if (stack->top == -1) {printf("Stack is empty.\n");return;}int value = stack->stack[stack->top--];removeMinHeap(&stack->minHeap);
}// 獲取棧頂元素
int top(Stack* stack) {if (stack->top == -1) {return -1;}return stack->stack[stack->top];
}// 獲取棧中的最小元素
int min(Stack* stack) {return getMin(&stack->minHeap);
}int main() {Stack stack;initStack(&stack);push(&stack, -1);push(&stack, 2);printf("MIN: %d\n", min(&stack));  // 輸出 -1printf("TOP: %d\n", top(&stack));  // 輸出 2pop(&stack);printf("TOP: %d\n", top(&stack));  // 輸出 -1printf("MIN: %d\n", min(&stack));  // 輸出 -1return 0;
}