【解锁单调栈奥秘】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言语实现单调栈，我们可能轻松处理求下一个更大年夜或更小元素的成绩。在现实编程中，纯熟控制单调栈的利用技能，将有助于我们处理更多复杂的成绩。