单调栈 acwing
时间: 2025-03-04 07:03:30 浏览: 70
### 单调栈算法简介
单调栈是一种特殊的栈结构,在处理某些特定问题时非常高效。其核心特点是保持栈内元素按照某种顺序排列,通常为递增或递减序列[^1]。
#### 单调栈的应用场景
当遇到如下特征的问题时可以考虑使用单调栈:
- 需要找到某个范围内最大/最小值的位置
- 寻找左侧第一个大于等于当前数的位置
- 查找右侧第一个小于当前位置数值的情况
这些问题在实际编程竞赛中较为常见,尤其是在涉及数组、链表等线性数据结构的操作上表现出色[^2]。
#### AcWing平台上的单调栈题目实例解析
##### 实例一:寻找下一个更大元素 (Next Greater Element)
给定两个没有重复数字的数组 `nums1` 和 `nums2` ,其中 `nums1` 是 `nums2` 的子集。对于每一个位于 `nums1[i]` 中的元素,在 `nums2` 数组里查找该位置右边的第一个更大的数;如果不存在,则返回 `-1` 。此题可以通过构建一个从右向左遍历并维护降序关系的单调栈来解决。
```python
def nextGreaterElement(nums1, nums2):
stack = []
res_map = {}
for num in reversed(nums2):
while stack and stack[-1] <= num:
stack.pop()
if not stack:
res_map[num] = -1
else:
res_map[num] = stack[-1]
stack.append(num)
result = [res_map[x] for x in nums1]
return result
```
上述代码实现了通过一次反向扫描建立映射表的功能,并利用了单调栈特性快速定位到目标值及其对应的最近较大值[^3]。
##### 实例二:柱状图中的最大矩形面积 (Largest Rectangle in Histogram)
这个问题要求在一个由多个宽度相同但高度不同的直方条组成的图形中找出能够构成的最大矩形区域。解决方案之一就是采用两次正逆双向遍历的方法配合单调栈实现高效的计算过程。
```python
def largestRectangleArea(heights):
heights.append(0) # 添加哨兵节点简化边界条件判断
stack = [-1]
max_area = 0
for i, h in enumerate(heights):
while heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
```
这段程序展示了如何巧妙运用单调栈技巧以及额外加入辅助元素的方式解决了复杂度较高的几何优化难题[^4]。
阅读全文
相关推荐
















