适用范围
单调栈主要解决以下问题：
- 寻找下一个更大元素
- 寻找前一个更大元素
- 寻找下一个更小元素
- 寻找前一个更小元素
- qualified 的 窗口的 max/min
- sliding window max/min
模板
单调栈的解题模式基本都是一样的，注意观察接下来的几道题解
一般都是这样：
Python
for 元素 in 列表:
while 栈不为空 and 栈顶元素（大于或者小于）目标值：
出栈
根据业务处理
入栈
实战
503. 下一个更大元素 I
Python
class Solution(object):
def nextGreaterElement(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
if not nums1 or not nums2:
return list()
# 单调递减栈：用于找到下一个更大的元素
stack = list()
# 因为题目说了没有重复元素，因此可以使用字典来维护元素的下一个更大元素：key-元素，value-下一个更大的元素
next_g_map = dict()
for num in nums2:
while stack and stack[-1] < num:
next_g_map[stack.pop()] = num
stack.append(num)
return [next_g_map.get(num, -1) for num in nums1]503. 下一个更大元素 II
# coding: utf-8
class Solution(object):
def nextGreaterElements(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return list()
# 因为是循环数组，这里直接采用扩容的方式，当然也可以直接通过取模在处理
nums2 = nums * 2
# 单调递减栈：用于找到下一个更大的元素
stack = [(0, nums2[0])]
# 维护元素的下一个更大元素
# 注：这个跟第一道题不同的是，可能有重复元素，因此不能使用字典来保存下一个更大元素
# 这里采用数组的形式
next_g = [-1] * len(nums2)
for index in range(1, len(nums2)):
num = nums2[index]
while stack and stack[-1][1] < num:
origin_index, _ = stack.pop()
# 通过原元素的索引来保存下一个更大元素
next_g[origin_index] = num
# 将原元素的索引保存下来
stack.append((index, num))
return next_g[:len(nums)]
42. 接雨水
Python
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height:
return 0
# 单调递减栈
stack = list()
rst = 0
for index in range(len(height)):
h = height[index]
# 只要找到一个比栈顶元素大的元素, 说明有可能形成了一个凹型
while stack and height[stack[-1]] < h:
# 凹型的右边
right_slide = stack.pop()
if stack:
# 栈里面还存在元素，说明形成了一个凹型，可以计算一个容量了：最低的高度 * 宽
rst += (min(height[stack[-1]], h) - height[
right_slide]) * (index - stack[-1] - 1)
stack.append(index)
return rst
739. 每日温度
Python
# coding: utf-8
class Solution(object):
def dailyTemperatures(self, T):
"""
:type T: List[int]
:rtype: List[int]
"""
if not T:
return []
# 单调递减栈
stack = []
rst = [0] * len(T)
for index in range(len(T)):
t = T[index]
# 循环遍历单调递减栈，直到栈中没有比当前元素小的值
while stack and stack[-1][1] < t:
# 找到一个匹配的递增对，将其出栈，并记录结果
origin_index, _ = stack.pop()
rst[origin_index] = index - origin_index
# 将索引保存下来，便于后面计算索引差
stack.append((index, t))
return rst901. 股票价格跨度
Python
class StockSpanner(object):
def __init__(self):
# 单调递减栈：存放元素及其跨度
self.prices = list()
def next(self, price):
"""
:type price: int
:rtype: int
"""
rst = 1
while self.prices and self.prices[-1][1] <= price:
# 找到了一个递增对，将其出栈（因为其历史跨度已经记录在了下一个元素中），并将其跨度叠加
rst += self.prices.pop()[0]
# 保持元素及其跨度，便于下一次直接计算历史跨度
self.prices.append((rst, price))
return rst
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)评论 (2)
