单调栈

什么是单调栈？

单调栈是一种在数据结构中非常实用的技术，主要应用于处理与顺序相关的优化问题。它利用栈的特点（先进后出），结合特定条件来保持栈内元素的递增或递减性。这种技术能够高效地解决一些复杂的算法问题，例如求解最大子数组和、计算最长上升子序列等。

单调栈的应用场景

1. 求解最值问题

单调栈在求解最值问题时非常有效。常见的应用包括寻找最大/最小元素及其位置、找到连续子数组的最大/小和等问题。

2. 哈希表或映射操作

有时，我们需要频繁地进行插入、删除以及查找操作，在这种情况下，使用单调栈可以优化时间复杂度。

3. 滑动窗口问题

在处理滑动窗口问题时（例如最大值最小值的连续子数组），单调栈能够帮助我们快速找到符合条件的答案。

单调栈的工作原理

单调栈的核心思想是通过维护一个严格递增或递减顺序的栈来解决特定的问题。具体来说，当元素被压入栈中前，会先检查当前元素与栈顶元素的关系；若不满足条件（如递增），则将栈顶元素弹出，并继续比较新的栈顶元素和新元素；这样可以保证在任意时刻栈内元素都保持单调性。

1. 入栈操作

• 当元素加入栈中时，检查当前元素是否大于栈顶元素。
• 如果小于或等于，则将其弹出直至满足条件再入栈。

2. 出栈操作

• 需要根据题目的需求来进行相应的处理。例如，在寻找最小区间问题中，当遇到符合条件的区间时记录相关信息。

示例：求解最大矩形面积

假设给你一个表示直方图的数组 heights，其中每个元素代表柱子的高度。你的任务是找到由这些柱子围成的最大矩形区域（高度为较短的那个柱子的高度）。

步骤：

1. 构造一个单调递增栈来保存柱子的下标。
2. 遍历数组 heights：
   • 如果当前柱子比栈顶高的柱子低，计算以栈顶元素为高的矩形面积，并更新最大值。
   • 将当前下标压入栈中。
3. 最后再检查一次栈，确保所有元素都被处理。

def largestRectangleArea(heights):
    stack = [-1]  # 哨兵节点
    max_area = 0
    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            cur_h = heights[stack.pop()]
            cur_w = i - stack[-1] - 1
            max_area = max(max_area, cur_h * cur_w)
        stack.append(i)
    # 处理剩余的柱子
    while stack[-1] != -1:
        cur_h = heights[stack.pop()]
        cur_w = len(heights) - stack[-1] - 1
        max_area = max(max_area, cur_h * cur_w)
    return max_area

总结

单调栈是一种高效解决特定问题的算法工具。它能够通过维护一个单调递增或递减的序列来简化复杂度，适用于多种场景下的最值、区间等问题。掌握好单调栈的应用技巧和思想，对提升编程能力和解决实际问题都有很大帮助。