Monotonic Stack

定义 Definition

单调栈：一种栈结构/技巧，使栈内元素始终保持单调递增或单调递减（通常按值或按索引对应的值）。常用于在数组/序列中高效求解“下一个更大/更小元素”、区间贡献、直方图最大矩形、滑动窗口相关变体等问题，典型时间复杂度为 **O(n)**。

发音 Pronunciation (IPA)

/ˌmɑːnəˈtɑːnɪk stæk/

例句 Examples

We used a monotonic stack to find the next greater element for each number.
我们用单调栈为每个数字找到它的下一个更大元素。

By maintaining a decreasing monotonic stack of indices, the algorithm computes each element’s contribution to subarray minima in linear time.
通过维护一个按索引对应值递减的单调栈，算法能在线性时间内计算每个元素对“所有子数组最小值”的贡献。

词源 Etymology

monotonic 来自希腊语词根 *mono-*（“单一”）与 tonos（“音调/张力”），引申为“单调地朝一个方向变化、保持单调性”。stack 指“栈式堆叠结构”。组合起来，monotonic stack 就是“保持单调性质的栈”。

相关词 Related Words

• Algorithm
• Data Structure
• Stack
• Monotonic Queue
• Next Greater Element
• Next Smaller Element
• Sliding Window
• Amortized Analysis
• Histogram
• Subarray

文学与作品 Literary Works

• Competitive Programming 4（Steven & Felix Halim）：在“栈/序列处理”与典型题型中常以单调栈思路讲解“Next Greater/Smaller”类问题。
• Elements of Programming Interviews（Aziz, Lee, Prakash）：在数组与栈相关章节中常出现以单调栈解决区间查询/“下一更大元素”范式的题解。
• LeetCode 题解与讨论合集（如 “Next Greater Element”, “Largest Rectangle in Histogram” 等题）：单调栈是高频标准解法之一。