正文

“掌握单调栈原理，轻松解决各种数据结构问题——实用模板解析及案例分析”

/0 浏览量
0403

单调栈是一种在解决某些数据结构问题时非常有效的算法。它通过维护一个栈，使得栈中的元素满足单调性（单调递增或单调递减）。这种数据结构可以帮助我们高效地解决一系列问题，如求区间最大值、最小值、下一个更大或更小的元素等。本文将深入解析单调栈的原理，并提供一些实用的模板和案例分析，帮助读者轻松掌握这一技巧。

单调栈的原理

单调栈的核心思想是维护一个单调的栈，通常有两种形式：

  1. 单调递增栈：栈中的元素从底部到顶部递增。
  2. 单调递减栈：栈中的元素从底部到顶部递减。

在处理问题时，我们通常从数组的右端开始向左端遍历，这样可以保证每次处理元素时，栈顶的元素都是当前遍历到的最大（或最小）元素。

单调栈的实用模板

以下是一些单调栈的常用模板，它们可以帮助我们解决各种问题：

模板一：求区间最大值

描述：给定一个数组 nums 和一个整数 k，求出所有长度为 k 的子数组中的最大值。

代码示例：

def maxSlidingWindow(nums, k):
    stack = []
    result = []
    for i in range(len(nums)):
        # 弹出小于当前元素的值
        while stack and stack[-1] < nums[i]:
            stack.pop()
        stack.append(nums[i])
        # 当栈顶元素对应的是窗口的第一个元素时，出栈
        if i >= k - 1:
            result.append(stack[0])
            if stack[0] == nums[i - k + 1]:
                stack.pop()
    return result

模板二：求下一个更大/更小的元素

描述：给定一个数组 nums，对于每个元素，找到它下一个更大/更小的元素。

代码示例：

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

案例分析

案例一：求一个数组中每个元素到下一个更大元素的距离

我们可以使用单调递减栈来解决此问题。

代码示例：

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

案例二：求一个数组中每个元素到下一个更小元素的距离

同样，我们可以使用单调递增栈来解决此问题。

代码示例：

def distanceToNextSmaller(nums):
    stack = []
    result = [-1] * len(nums)
    for i in range(len(nums) - 1, -1, -1):
        while stack and stack[-1] >= nums[i]:
            stack.pop()
        if stack:
            result[i] = i - stack[-1]
        stack.append(nums[i])
    return result

通过以上模板和案例分析，我们可以看到单调栈在解决数据结构问题时的强大能力。掌握这一技巧，可以帮助我们在面对类似问题时更加得心应手。

-- 展开阅读全文 --