Python实现单调栈：从基础到最佳实践

简介

在算法和数据结构的领域中，单调栈是一种强大且独特的数据结构，它在处理一些需要寻找特定元素关系的问题时表现出色。通过维护栈内元素的单调性（递增或递减），单调栈能够在线性时间内解决许多看似复杂的问题。本文将深入探讨如何使用Python实现单调栈，并介绍其使用方法、常见实践以及最佳实践，帮助读者掌握这一高效的数据结构。

目录

1. 单调栈基础概念
2. Python实现单调栈
3. 单调栈使用方法
4. 常见实践
5. 最佳实践
6. 小结
7. 参考资料

单调栈基础概念

单调栈是一种特殊的数据结构，它的主要特点是栈内元素保持单调递增或单调递减的顺序。单调栈通常分为单调递增栈和单调递减栈：

• 单调递增栈：栈内元素从栈底到栈顶单调递增，新元素入栈时，会将栈顶大于它的元素依次弹出，直到栈顶元素小于等于新元素或者栈为空。
• 单调递减栈：栈内元素从栈底到栈顶单调递减，新元素入栈时，会将栈顶小于它的元素依次弹出，直到栈顶元素大于等于新元素或者栈为空。

单调栈的优势在于能够在一次遍历数组时，高效地找到每个元素的一些特定关系，例如找到每个元素左侧或右侧第一个比它大或者小的元素。

Python实现单调栈

单调递增栈实现

def increasing_monotonic_stack(nums):
    stack = []
    result = []
    for num in nums:
        while stack and stack[-1] > num:
            stack.pop()
        stack.append(num)
        result.append(stack[:])
    return result


nums = [3, 2, 5, 1, 4]
print(increasing_monotonic_stack(nums))

单调递减栈实现

def decreasing_monotonic_stack(nums):
    stack = []
    result = []
    for num in nums:
        while stack and stack[-1] < num:
            stack.pop()
        stack.append(num)
        result.append(stack[:])
    return result


nums = [3, 2, 5, 1, 4]
print(decreasing_monotonic_stack(nums))

单调栈使用方法

1. 初始化栈：创建一个空栈，用于存储元素。
2. 遍历数组：依次遍历数组中的每个元素。
3. 处理元素：对于每个元素，根据单调栈的类型（递增或递减），将栈顶不符合单调性的元素弹出，直到栈顶元素满足单调性或者栈为空。
4. 入栈：将当前元素压入栈中。
5. 记录结果（可选）：根据具体问题的需求，可以在每个元素入栈后记录栈的状态或者相关信息。

常见实践

寻找下一个更大元素

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

def next_greater_element(nums):
    stack = []
    result = [-1] * len(nums)
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            index = stack.pop()
            result[index] = nums[i]
        stack.append(i)
    return result


nums = [1, 3, 2, 4]
print(next_greater_element(nums))

计算柱状图中最大矩形面积

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

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    i = 0
    while i <= len(heights):
        height = 0 if i == len(heights) else heights[i]
        while stack and height < heights[stack[-1]]:
            h = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * width)
        stack.append(i)
        i += 1
    return max_area


heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))

最佳实践

1. 优化空间复杂度：在实现单调栈时，尽量减少额外空间的使用。例如，在寻找下一个更大元素的问题中，直接在结果数组中记录答案，而不是使用额外的数据结构来存储中间结果。
2. 处理边界情况：在处理单调栈时，要特别注意边界情况，如数组为空、栈为空等情况，确保代码的鲁棒性。
3. 结合其他数据结构：根据具体问题，可以将单调栈与其他数据结构（如哈希表）结合使用，以提高算法的效率。

小结

单调栈是一种高效的数据结构，通过维护栈内元素的单调性，能够在线性时间内解决许多与元素关系相关的问题。本文介绍了单调栈的基础概念、Python实现方法、使用方法、常见实践以及最佳实践。希望读者通过阅读本文，能够深入理解单调栈，并在实际编程中灵活运用，解决各种算法问题。

参考资料

• 《算法导论》
• LeetCode相关题目：496. 下一个更大元素 I，84. 柱状图中最大的矩形