一.什么是单调栈？
- 栈内元素单调的栈，分为单调递增或者单调递减两种。
二.什么时候用这种特殊的结构？
- 在需要通过比较数组或者队列的前后元素来解决问题时。
三.介绍一下两种栈
1.单调递增栈
- 针对列表中每一个元素从它右边开始查找第一个比它小的元素。
- 针对列表中每一个元素从它左边开始查找第一个比它小的元素。（从后往前遍历）
- 例题：
leetcode:
896. 单调数列
84. 柱状图中最大的矩形
2.单调递减栈
- 针对列表中每一个元素从它右边开始查找第一个比它大的元素。
- 针对列表中每一个元素从它左边开始查找第一个比它小的元素。（从后往前开始遍历）
- 例题：
leetcode:
1019. 链表中的下一个更大节点
496. 下一个更大元素 I
503. 下一个更大元素 II
739. 每日温度
901. 股票价格跨度
四.实战招数
单调栈该怎么用？
从题目抽象出来的具体问题一般可以分为两步：
1.怎么快速的找到元素两侧第一个符合要求的元素
2.怎么把找到的结果储存起来-
实际会遇到的情况？
待处理的列表一般有两种形式，一种是元素不重复，一种是元素重复，或元素需要查询的结果和初始列表位置相关。- 元素不重复的可以用字典来存储查询结果，查找速度快。
- 元素重复的，或者答案依赖位置的，要用列表来存储结果，有一些找不到位置的，可以在初始化的时候就进行填充。
流程图
屏幕快照 2022-01-03 下午8.07.19.png
五.练兵
"""496. 下一个更大元素 I
难度
简单
619
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？"""
-题解-
class Solution:
def nextGreaterElement(self, nums1, nums2):
"""
设计好套路准备函数
:param nums1:
:param nums2:
:return:
"""
# 传入
res = self.monotonic_stack(nums2)
# 拼凑答案
ans = []
for each in nums1:
if res.get(each):
ans.append(res.get(each))
else:
ans.append(-1)
return ans
def monotonic_stack(self,nums2):
"""
专门处理查询+储存
:param nums2:
:return:
"""
n = len(nums2)
stack = []
res = {}
for i in range(n):
while stack and stack[-1] < nums2[i]:
tmp = stack.pop()
res[tmp] = nums2[i]
stack.append(nums2[i])
return res
nums1 = [4,1,2]
nums2 = [1,3,4,2]
a = Solution().nextGreaterElement(nums1,nums2)
print(a)
这个题目的特点：没有重复元素
所以可以，用字典来存储
"""503. 下一个更大元素 II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。"""```
-题解-
class Solution:
def nextGreaterElements(self, nums):
"""
:param nums:
:return:
"""
lenth = len(nums)
# 循环数组的朴素处理方法，拼接
for i in range(lenth):
nums.append(nums[i])
# 输入
res = self.monotonic_stack(nums,lenth)
return res[0:lenth]
def monotonic_stack(self,nums,lenth):
"""
专门处理加储存
:param nums:
:param lenth:
:return:
"""
lenth = lenth *2
# 因为是有序的且有重复的，所以用列表来存储答案
res = [-1]*lenth
stack = []
for i in range(lenth):
while stack and nums[stack[-1]] <nums[i]:
ind = stack.pop()
# 存位置
res[ind] = nums[i]
stack.append(i)
return res
nums = [1, 2, 1]
print(s.nextGreaterElements(nums))
"""739. 每日温度
请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100"""```
-题解-
class Solution:
def dailyTemperatures(self,temperatures):
res = self.monotonic_stack(temperatures)
n = len(temperatures)
for i in range(n):
if res[i]!=0:
res[i] = res[i]-i
return res
def monotonic_stack(self, temperatures):
lenth = len(temperatures)
stack =[]
res = [0]*lenth
for i in range(lenth):
while stack and temperatures[stack[-1]] < temperatures[i]:
index = stack.pop()
res[index] = i
stack.append(i)
return res
"""901. 股票价格跨度
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
示例：
输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。
提示：
调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用 10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。"""
class StockSpanner:
def __init__(self):
self.stack = []
self.prices = []
def next(self, price):
"""
:param price:
:return:
"""
# 处理输入
self.prices.append(price)
# 传入输入
res = self.monotonic_stack(price)
return res
def monotonic_stack(self, price):
"""
:param price:
:return:
"""
# 价格是每次才传进来的
n = len(self.prices)-1
# 天数跨度默认为1，跨度要每次计算，跨度要和价格一一对应，这些都要存下来
day = 1
while self.stack and price >= self.prices[self.stack[-1][0]]:
inx = self.stack.pop()
# 弹出的时候，加上被弹出项的跨度
day += inx[1]
self.stack.append((n,day))
return day
s = StockSpanner()
nums = [100, 80, 60, 70, 60, 75, 85]
ans = []
for each in nums:
res = s.next(each)
# 处理输出
ans.append(res)
print(ans)```
