单调栈算法实现 c语言

单调栈算法是一种常用的数据结构算法，主要用于处理与数组或列表相关的某些问题，特别是涉及到寻找数组中某个元素左边或右边最近的比它大或小的元素的问题。单调栈分为单调递增栈和单调递减栈。单调递增栈是指栈中的元素从栈底到栈顶保持递增的顺序，单调递减栈则相反。

以下是使用C语言实现单调递增栈的基本步骤：

1. 定义一个栈，并初始化一个数组来模拟栈的行为。
2. 遍历数组或列表中的每一个元素。
3. 对于每个元素，检查栈顶元素是否大于当前元素。
- 如果栈顶元素大于当前元素，那么将栈顶元素的索引从栈中移除，并记录当前元素是栈顶元素右边第一个比它小的元素。
- 重复这个过程，直到栈为空或者栈顶元素小于等于当前元素。
4. 将当前元素的索引压入栈中。
5. 重复步骤2-4，直到处理完所有元素。

下面是一个C语言实现单调递增栈的简单示例代码：

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

// 定义栈结构体
typedef struct {
    int *data;
    int top;
    int capacity;
} Stack;

// 初始化栈
Stack* createStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (int*)malloc(sizeof(int) * capacity);
    stack->capacity = capacity;
    stack->top = -1;
    return stack;
}

// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 入栈
void push(Stack *stack, int value) {
    if (stack->top < stack->capacity - 1) {
        stack->data[++stack->top] = value;
    }
}

// 出栈
int pop(Stack *stack) {
    if (!isEmpty(stack)) {
        return stack->data[stack->top--];
    }
    return -1; // 栈为空时返回-1
}

// 获取栈顶元素，但不出栈
int peek(Stack *stack) {
    if (!isEmpty(stack)) {
        return stack->data[stack->top];
    }
    return -1;
}

// 单调递增栈算法示例
void monotonicIncreasingStack(int *arr, int n) {
    Stack *stack = createStack(n);
    for (int i = 0; i < n; i++) {
        while (!isEmpty(stack) && arr[stack->top] > arr[i]) {
            printf("元素 %d 的右边第一个小于它的元素是 %d\n", arr[stack->top], arr[i]);
            pop(stack);
        }
        push(stack, i);
    }
    // 清理栈内存
    free(stack->data);
    free(stack);
}

int main() {
    int arr[] = {3, 1, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    monotonicIncreasingStack(arr, n);
    return 0;
}

在这个示例中，我们使用了一个辅助函数 `monotonicIncreasingStack` 来实现单调递增栈算法。该函数接受一个数组和数组的长度，然后打印出每个元素右边第一个小于它的元素。