一、啥是单调栈和单调队列
咱先来说说单调栈和单调队列是啥。单调栈就是一种特殊的栈，栈里面的元素是单调递增或者单调递减的。就好比排队，后面的人要么比前面的人高，要么比前面的人矮，不能乱了顺序。单调队列呢，和单调栈有点像，不过它是队列，元素也是单调的。
举个例子，有一个数组 [3, 1, 4, 2]，我们用单调递增栈来处理它。一开始栈是空的，把 3 放进去，栈里就是 [3]。接着是 1，因为 1 比 3 小，符合单调递增的规则，就把 1 压入栈，栈变成 [3, 1]。然后是 4，4 比 1 大，不符合单调递增了，就把 1 弹出来，再把 4 压入栈，栈变成 [3, 4]。最后是 2，2 比 4 小，但是比 3 大，就把 2 压入栈，栈最终是 [3, 4, 2]。
以下是用 Python 实现的单调递增栈的代码示例：
# Python 技术栈
stack = []
nums = [3, 1, 4, 2]
for num in nums:
# 当栈不为空且栈顶元素大于当前元素时，弹出栈顶元素
while stack and stack[-1] > num:
stack.pop()
stack.append(num)
print(stack) # 输出 [3, 4, 2]
二、滑动窗口最大值问题
问题描述
滑动窗口最大值问题是这样的：给定一个数组和一个固定大小的窗口，窗口在数组上滑动，每次滑动一个位置，求每个窗口内的最大值。
示例
假设有数组 [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小是 3。那么第一个窗口是 [1, 3, -1]，最大值是 3；第二个窗口是 [3, -1, -3]，最大值是 3；第三个窗口是 [-1, -3, 5]，最大值是 5，以此类推。
用单调队列解决
我们可以用单调队列来解决这个问题。单调队列里存储的是数组元素的下标，队列里的元素对应的数组值是单调递减的。
以下是用 Python 实现的代码：
# Python 技术栈
from collections import deque
def maxSlidingWindow(nums, k):
result = []
queue = deque()
for i in range(len(nums)):
# 当队列不为空且队列头部元素已经不在当前窗口内时，移除头部元素
if queue and queue[0] == i - k:
queue.popleft()
# 当队列不为空且队列尾部元素对应的数组值小于当前元素时，移除尾部元素
while queue and nums[queue[-1]] < nums[i]:
queue.pop()
# 将当前元素的下标加入队列
queue.append(i)
# 当窗口形成后，将队列头部元素对应的数组值加入结果列表
if i >= k - 1:
result.append(nums[queue[0]])
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(maxSlidingWindow(nums, k)) # 输出 [3, 3, 5, 5, 6, 7]
三、下一个更大元素问题
问题描述
下一个更大元素问题是：对于数组中的每个元素，找到它右边第一个比它大的元素。如果没有，就用 -1 表示。
示例
比如数组 [2, 1, 2, 4, 3]，对于元素 2，它右边第一个比它大的元素是 4；对于元素 1，右边第一个比它大的元素是 2；对于元素 2，右边第一个比它大的元素是 4；对于元素 4，右边没有比它大的元素，用 -1 表示；对于元素 3，右边没有比它大的元素，用 -1 表示。所以结果是 [4, 2, 4, -1, -1]。
用单调栈解决
我们可以用单调栈来解决这个问题。从左到右遍历数组，把元素压入栈，如果当前元素比栈顶元素大，就说明栈顶元素的下一个更大元素就是当前元素。
以下是用 Python 实现的代码：
# Python 技术栈
def nextGreaterElements(nums):
result = [-1] * len(nums)
stack = []
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 = [2, 1, 2, 4, 3]
print(nextGreaterElements(nums)) # 输出 [4, 2, 4, -1, -1]
四、应用场景
滑动窗口最大值的应用场景
- 股票分析：在股票价格数据中，我们可以用滑动窗口最大值来分析一段时间内的最高股价，帮助投资者判断股票的走势。
- 信号处理：在信号处理中，滑动窗口最大值可以用于去除噪声，找到信号中的峰值。
下一个更大元素的应用场景
- 温度预测：在气象数据中，我们可以用下一个更大元素来预测未来一段时间内的最高温度。
- 物流调度：在物流调度中，我们可以用下一个更大元素来安排货物的运输顺序。
五、技术优缺点
单调栈的优缺点
- 优点：
- 时间复杂度低，通常是 O(n)，因为每个元素最多进栈和出栈一次。
- 代码实现简单，逻辑清晰。
- 缺点：
- 只适用于处理单调问题，如果数据不是单调的，可能需要额外的处理。
- 空间复杂度较高，需要使用栈来存储元素。
单调队列的优缺点
- 优点：
- 同样时间复杂度低，也是 O(n)。
- 可以高效地处理滑动窗口问题。
- 缺点：
- 实现相对复杂一些，需要使用队列来存储元素。
- 对于非滑动窗口问题，可能不太适用。
六、注意事项
单调栈的注意事项
- 在使用单调栈时，要注意栈的边界条件，避免栈为空时进行弹出操作。
- 对于不同的问题，可能需要调整单调栈的单调性，比如单调递增栈或单调递减栈。
单调队列的注意事项
- 在使用单调队列时，要注意队列的头部元素是否已经不在当前窗口内，需要及时移除。
- 队列的更新操作要保证元素的单调性。
七、文章总结
单调栈和单调队列是非常有用的数据结构，它们可以高效地解决滑动窗口最大值和下一个更大元素等问题。单调栈适用于处理单调问题，通过维护栈的单调性来找到元素之间的关系；单调队列则更适合处理滑动窗口问题，通过维护队列的单调性来快速找到窗口内的最大值。在实际应用中，我们可以根据具体问题选择合适的数据结构，同时要注意它们的优缺点和使用注意事项。
评论