【解锁单调栈奥秘】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语言实现单调栈，我们可以轻松解决求下一个更大或更小元素的问题。在实际编程中，熟练掌握单调栈的使用技巧，将有助于我们解决更多复杂的问题。