单调栈应用c语言

单调栈是一种特殊的栈结构，用于高效解决**下一个更大元素**、**柱状图最大矩形**等经典问题。其核心思想是通过维护栈的单调性（递增或递减），避免重复计算。以下是C语言中单调栈的详细实现及应用示例： --- ### **1. 单调栈的基本实现** #### **模板代码（递增单调栈）** ```c #include <stdio.h> #include <stdlib.h> // 单调栈结构 typedef struct { int *data; // 存储栈元素 int *indices; // 可选：存储元素下标（用于某些问题） int top; // 栈顶指针 int capacity; // 栈容量 } MonotonicStack; // 初始化栈 MonotonicStack* createStack(int capacity) { MonotonicStack *stack = (MonotonicStack*)malloc(sizeof(MonotonicStack)); stack->data = (int*)malloc(sizeof(int) * capacity); stack->indices = (int*)malloc(sizeof(int) * capacity); // 可选 stack->top = -1; stack->capacity = capacity; return stack; } // 入栈（维护单调递增） void push(MonotonicStack *stack, int value, int index) { while (stack->top >= 0 && stack->data[stack->top] >= value) { pop(stack); // 弹出破坏单调性的元素 } stack->data[++stack->top] = value; stack->indices[stack->top] = index; // 可选：记录下标 } // 出栈 int pop(MonotonicStack *stack) { if (stack->top == -1) return -1; // 栈空 return stack->data[stack->top--]; } // 获取栈顶元素 int peek(MonotonicStack *stack) { if (stack->top == -1) return -1; return stack->data[stack->top]; } // 释放栈 void freeStack(MonotonicStack *stack) { free(stack->data); free(stack->indices); free(stack); } ``` --- ### **2. 经典应用示例** #### **示例1：下一个更大元素（LeetCode 496）** 给定数组 `nums1` 和 `nums2`，找出 `nums1` 中每个元素在 `nums2` 中的下一个更大元素。 ```c #include <stdio.h> #include <stdlib.h> int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) { // 哈希表记录nums2中元素的下一个更大值 int hash[10000] = {0}; // 假设元素范围在0-9999 MonotonicStack *stack = createStack(nums2Size); // 预处理nums2：构建单调栈并记录结果 for (int i = 0; i < nums2Size; i++) { while (stack->top != -1 && stack->data[stack->top] < nums2[i]) { hash[stack->data[stack->top]] = nums2[i]; // 记录下一个更大值 pop(stack); } push(stack, nums2[i], i); // 当前元素入栈 } // 处理栈中剩余元素（无下一个更大值） while (stack->top != -1) { hash[stack->data[stack->top]] = -1; pop(stack); } // 生成结果 int *result = (int*)malloc(sizeof(int) * nums1Size); *returnSize = nums1Size; for (int i = 0; i < nums1Size; i++) { result[i] = hash[nums1[i]]; } freeStack(stack); return result; } ``` #### **示例2：柱状图中的最大矩形（LeetCode 84）** 计算柱状图中能形成的最大矩形面积。 ```c int largestRectangleArea(int* heights, int heightsSize) { if (heightsSize == 0) return 0; // 添加哨兵值简化代码 int *newHeights = (int*)malloc(sizeof(int) * (heightsSize + 2)); newHeights[0] = 0; for (int i = 0; i < heightsSize; i++) { newHeights[i + 1] = heights[i]; } newHeights[heightsSize + 1] = 0; heightsSize += 2; MonotonicStack *stack = createStack(heightsSize); int maxArea = 0; for (int i = 0; i < heightsSize; i++) { // 当前高度小于栈顶高度时，计算面积 while (stack->top != -1 && newHeights[i] < newHeights[peek(stack)]) { int height = newHeights[pop(stack)]; int width = i - peek(stack) - 1; // 左右边界差 maxArea = (height * width > maxArea) ? height * width : maxArea; } push(stack, i, i); // 存储下标而非高度 } freeStack(stack); free(newHeights); return maxArea; } ``` --- ### **3. 关键点说明** 1. **单调性维护**： - **递增栈**：用于找**下一个更大元素**（栈顶是最小值）。 - **递减栈**：用于找**下一个更小元素**（栈顶是最大值）。 2. **应用场景**： - 需要快速找到数组中某个元素左右边界的问题（如最大矩形、每日温度）。 - 时间复杂度优化：从暴力 \(O(n^2)\) 降至 \(O(n)\)。 3. **边界处理**： - 在数组首尾添加**哨兵值**（如 `0`）简化栈的清空逻辑。 - 使用下标而非值入栈，方便计算宽度。 --- ### **4. 完整示例（每日温度）** 给定温度数组，返回每天需要等待多少天才能遇到更暖的温度。 ```c int* dailyTemperatures(int* temperatures, int size, int* returnSize) { *returnSize = size; int *result = (int*)calloc(size, sizeof(int)); // 初始化为0 MonotonicStack *stack = createStack(size); for (int i = 0; i < size; i++) { while (stack->top != -1 && temperatures[i] > temperatures[peek(stack)]) { int prevIndex = pop(stack); result[prevIndex] = i - prevIndex; // 更新等待天数 } push(stack, i, i); // 存储下标 } freeStack(stack); return result; } ``` --- ### **5. 常见问题** #### **Q1：单调栈为什么需要维护单调性？** - 保证栈顶元素是当前未处理元素的“最近”极大值/极小值，避免重复遍历。 #### **Q2：如何选择递增或递减栈？** - 找**下一个更大元素** → 递增栈（弹出比当前小的元素）。 - 找**下一个更小元素** → 递减栈（弹出比当前大的元素）。 #### **Q3：为什么柱状图问题需要哨兵值？** - 确保栈中所有元素最终被处理（避免最后残留元素无法弹出）。 ---