題目描述

定義棧的資料結構，請在該型別中實現一個能夠得到棧的最小元素的 min 函式在該棧中，呼叫 min、push 及 pop 的時間複雜度都是 O(1)。

這道題目是我在位元組面試時遇到的真題，當初沒想到最優解，覆盤的時候發現是道簡單題。。把這道題目作為棧的使用分享給大家！（在面試的時候沒有想到最優解就先選擇一個次優的解法，總比做不出來要好!)

LeetCode：劍指 Offer 30. 包含 min 函式的棧

棧可以看作是一個數組，在一個數組中找一個最值是很簡單的，我們只需要遍歷這個陣列即可。在要求 O(1)時間內時，我們在進行陣列賦值的時候記錄下最值即可滿足要求。但是要求在元素髮生變動的時候也滿足 O(1)的話，我們可以儲存每次入棧時的最值。即用空間換時間！

圖解：

--------------------------------values | 0 | -1 | 10 | -2 | -2 |--------------------------------min    | 0 | -1 | -1 | -2 | -2 |--------------------------------

從註釋中可以看出，我們在新增元素的時候將傳入的值與當前棧的最值進行判斷即可得知在新增新元素之後棧的最值

#include <stdio.h>#include <stdlib.h>typedef struct MinStack{    /* data */    int len;     // 元素長度    int index;   // 新元素下標    int *values; // 值陣列    int *min;    // 最值陣列} MinStack;// 初始化MinStack *init(int size){    // 申請空間    MinStack *stack = malloc(sizeof(MinStack));    // 初始化值    stack->index = 0;    stack->len = 0;    stack->values = malloc(sizeof(int) * size);    stack->min = malloc(sizeof(int) * size);    return stack;}//  入棧操作void push(MinStack *stack, int val){    // 指標為空直接返回    if (stack == NULL)    {        return;    }    // 將元素進行儲存    stack->values[stack->index] = val;    // 判斷最值    if (stack->len > 0)    {        // 存在元素就與當前棧的最值進行比較        int lastMin = stack->min[stack->index - 1];        if (lastMin < val)        {            stack->min[stack->index] = lastMin;        }        else        {            stack->min[stack->index] = val;        }    }    else    {        // 棧為空直接設定為最值        stack->min[stack->index] = val;    }    stack->index++;    stack->len++;}// 出棧操作int pop(MinStack *stack){    // 棧為空    if (stack == NULL || stack->len < 1)    {        return 0xFFFFFF;    }    // 出棧    int val = stack->values[stack->index - 1];    // 更新下標和長度    stack->len--;    stack->index--;    return val;}// 獲取最小值int min(MinStack *stack){    // 直接返回最值    return stack->min[stack->index - 1];}// 銷燬棧物件void destory(MinStack *stack){    //釋放空間 重置資料    stack->index = stack->len = 0;    free(stack->min);    free(stack->values);}

int main(){    MinStack *stack = init(100);    push(stack, 1);    printf("min=%d\n", min(stack));    push(stack, -1);    push(stack, 100);    printf("min=%d\n", min(stack));    printf("pop=%d\n", pop(stack));    printf("len=%d\n", stack->len);    return 0;}

最近我也在用 Go 刷演算法題攢程式碼熟練度，再結合一些資料結構的知識新開了這個系列。後續將會繼續更新！

以上就是本期的全部內容，感謝你的閱讀！我們春節見，會有一些大的改動以及總結和在牛年的一些計劃！