深入探索：C语言实现单调栈

简介

在算法和数据结构的世界中，单调栈是一种强大且高效的数据结构，常用于解决与数组元素顺序和比较相关的问题。它在处理需要维护元素单调性（递增或递减）的场景下表现出色。本文将深入探讨如何使用C语言实现单调栈，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一重要工具。

目录

1. 单调栈基础概念
2. C语言实现单调栈
   • 基本结构与初始化
   • 入栈与出栈操作
3. 单调栈使用方法
   • 寻找下一个更大元素
   • 寻找下一个更小元素
4. 常见实践
   • 计算柱状图的最大面积
   • 股票价格问题
5. 最佳实践
   • 代码优化与注意事项
   • 时间复杂度与空间复杂度分析
6. 小结
7. 参考资料

单调栈基础概念

单调栈是一种特殊的数据结构，它的特点在于栈内元素的单调性。单调栈分为单调递增栈和单调递减栈：

• 单调递增栈：栈内元素从栈底到栈顶严格递增。当新元素小于栈顶元素时，栈顶元素出栈，直到新元素大于等于栈顶元素或栈为空，然后新元素入栈。
• 单调递减栈：栈内元素从栈底到栈顶严格递减。当新元素大于栈顶元素时，栈顶元素出栈，直到新元素小于等于栈顶元素或栈为空，然后新元素入栈。

单调栈常用于解决寻找数组中某个元素的下一个更大或更小元素的问题，能够在 $O(n)$ 的时间复杂度内完成操作，相比暴力解法具有显著的性能提升。

C语言实现单调栈

基本结构与初始化

首先，我们需要定义一个栈的数据结构，并初始化栈。在C语言中，可以使用数组和一个变量来模拟栈的操作。

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

#define MAX_SIZE 1000

// 定义栈结构
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

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

// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

入栈与出栈操作

接下来，实现栈的入栈和出栈操作。

// 入栈操作
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->data[++(s->top)] = value;
}

// 出栈操作
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1; // 返回一个错误值
    }
    return s->data[(s->top)--];
}

// 获取栈顶元素
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1; // 返回一个错误值
    }
    return s->data[s->top];
}

单调栈使用方法

寻找下一个更大元素

给定一个数组，对于每个元素，找到它在数组中右侧第一个比它大的元素。

void nextGreaterElement(int arr[], int n) {
    Stack s;
    initStack(&s);
    int result[n];

    for (int i = n - 1; i >= 0; i--) {
        while (!isEmpty(&s) && peek(&s) <= arr[i]) {
            pop(&s);
        }
        if (isEmpty(&s)) {
            result[i] = -1; // 没有找到下一个更大元素
        } else {
            result[i] = peek(&s);
        }
        push(&s, arr[i]);
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
}

寻找下一个更小元素

类似地，我们可以找到每个元素在数组中右侧第一个比它小的元素。

void nextSmallerElement(int arr[], int n) {
    Stack s;
    initStack(&s);
    int result[n];

    for (int i = n - 1; i >= 0; i--) {
        while (!isEmpty(&s) && peek(&s) >= arr[i]) {
            pop(&s);
        }
        if (isEmpty(&s)) {
            result[i] = -1; // 没有找到下一个更小元素
        } else {
            result[i] = peek(&s);
        }
        push(&s, arr[i]);
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
}

常见实践

计算柱状图的最大面积

给定一个表示柱状图高度的数组，计算柱状图中能够围成的最大矩形面积。

int largestRectangleArea(int heights[], int n) {
    Stack s;
    initStack(&s);
    int maxArea = 0;
    int i = 0;

    while (i < n) {
        if (isEmpty(&s) || heights[peek(&s)] <= heights[i]) {
            push(&s, i++);
        } else {
            int topIndex = pop(&s);
            int width = isEmpty(&s)? i : i - peek(&s) - 1;
            maxArea = maxArea > heights[topIndex] * width? maxArea : heights[topIndex] * width;
        }
    }

    while (!isEmpty(&s)) {
        int topIndex = pop(&s);
        int width = isEmpty(&s)? i : i - peek(&s) - 1;
        maxArea = maxArea > heights[topIndex] * width? maxArea : heights[topIndex] * width;
    }

    return maxArea;
}

股票价格问题

给定一个表示股票价格的数组，计算每个交易日能够获得的最大利润（当天买入，第二天卖出）。

int maxProfit(int prices[], int n) {
    Stack s;
    initStack(&s);
    int maxProfit = 0;

    for (int i = 0; i < n; i++) {
        while (!isEmpty(&s) && prices[peek(&s)] >= prices[i]) {
            pop(&s);
        }
        if (!isEmpty(&s)) {
            maxProfit = maxProfit > prices[i] - prices[peek(&s)]? maxProfit : prices[i] - prices[peek(&s)];
        }
        push(&s, i);
    }

    return maxProfit;
}

最佳实践

代码优化与注意事项

• 边界检查：在进行入栈、出栈和访问栈顶元素操作时，务必进行边界检查，防止栈溢出和栈下溢错误。
• 内存管理：如果使用动态内存分配来实现栈，要注意及时释放内存，避免内存泄漏。
• 效率提升：在处理大规模数据时，可以考虑使用更高效的数据结构或算法优化策略，例如使用链表实现栈以避免数组的固定大小限制。

时间复杂度与空间复杂度分析

• 时间复杂度：单调栈的操作通常在 $O(n)$ 的时间复杂度内完成，因为每个元素最多入栈和出栈一次。
• 空间复杂度：空间复杂度取决于栈中最多存储的元素个数，最坏情况下为 $O(n)$。

小结

本文详细介绍了单调栈的基础概念、C语言实现方法、使用场景以及最佳实践。通过理解和掌握单调栈，我们能够高效地解决许多与数组元素顺序和比较相关的问题。希望读者通过实践本文中的代码示例，能够熟练运用单调栈解决实际问题。

参考资料

• 《算法导论》
• LeetCode官方文档
• GeeksforGeeks相关文章