【解鎖單調棧奧秘】C語言高效解題技巧揭秘

單調棧是一種特其余棧，它保護一個元素的次序，要麼壹直遞增，要麼壹直遞減。單調棧在處理某些算法成績時非常有效，比方求一個序列的下一個更大年夜或更小的元素。在C言語中，我們可能經由過程實現單調棧來高效處理這些成績。

單調棧的不雅點

單調棧是一種只容許拔出跟刪除操縱，並且棧內元素保持單調性的棧。單調棧可能是遞增的，也可能是遞減的。在遞增棧中，每個元素都大年夜於或等於其前面的元素；在遞減棧中，每個元素都小於或等於其前面的元素。

單調棧的C言語實現

以下是一個遞增單調棧的C言語實現：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *elements;
    int top;
    int capacity;
} MonotonicStack;

// 初始化單調棧
void StackInit(MonotonicStack *stack, int capacity) {
    stack->elements = (int *)malloc(capacity * sizeof(int));
    stack->top = -1;
    stack->capacity = capacity;
}

// 燒毀單調棧
void StackDestroy(MonotonicStack *stack) {
    free(stack->elements);
    stack->elements = NULL;
    stack->top = -1;
    stack->capacity = 0;
}

// 入棧
void Push(MonotonicStack *stack, int value) {
    if (stack->top == stack->capacity - 1) {
        printf("Stack overflow\n");
        return;
    }
    stack->elements[++stack->top] = value;
}

// 出棧
int Pop(MonotonicStack *stack) {
    if (stack->top == -1) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack->elements[stack->top--];
}

// 檢查棧能否為空
int IsEmpty(MonotonicStack *stack) {
    return stack->top == -1;
}

// 獲取棧頂元素
int Peek(MonotonicStack *stack) {
    if (stack->top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->elements[stack->top];
}

單調棧的利用

求下一個更大年夜元素

給定一個整數數組 nums，前去每個元素前面比它大年夜的第一個元素。

void NextGreaterElement(int *nums, int numsSize, int *result) {
    MonotonicStack stack;
    StackInit(&stack, numsSize);
    for (int i = numsSize - 1; i >= 0; i--) {
        while (!IsEmpty(&stack) && stack.elements[stack.top] <= nums[i]) {
            Pop(&stack);
        }
        result[i] = IsEmpty(&stack) ? -1 : stack.elements[stack.top];
        Push(&stack, nums[i]);
    }
    StackDestroy(&stack);
}

求下一個更小元素

給定一個整數數組 nums，前去每個元素前面比它小的第一個元素。

void NextSmallerElement(int *nums, int numsSize, int *result) {
    MonotonicStack stack;
    StackInit(&stack, numsSize);
    for (int i = 0; i < numsSize; i++) {
        while (!IsEmpty(&stack) && stack.elements[stack.top] >= nums[i]) {
            Pop(&stack);
        }
        result[i] = IsEmpty(&stack) ? -1 : stack.elements[stack.top];
        Push(&stack, nums[i]);
    }
    StackDestroy(&stack);
}

總結

單調棧是一種高效的數據構造，在處理某些算法成績時非常有效。經由過程C言語實現單調棧，我們可能輕鬆處理求下一個更大年夜或更小元素的成績。在現實編程中，純熟控制單調棧的利用技能，將有助於我們處理更多複雜的成績。