单调栈是指栈内元素（栈底到栈顶）都是（严格）单调递增或者单调递减的。
如果有新的元素入栈，栈调整过程中 会将所有破坏单调性的栈顶元素出栈，并且出栈的元素不会再次入栈 。由于每个元素只有一次入栈和出栈的操作，所以 单调栈的维护时间复杂度是O(n) 。
单调栈性质：
- 单调栈里的元素具有单调性。
- 递增（减）栈中可以找到元素左右两侧比自身小（大）的第一个元素。
利用这两个性质可以实现对于某个元素：
- 左边区间第一个比它小的数，第一个比它大的数
- 确定这个元素是否是区间最值
- 右边区间第一个大于它的值到该值的距离
- 确定以该元素为最值的最长区间
初始化一个stack
遍历数组:
while stack and 栈顶元素和当前值的比较：
出栈
根据题意一顿操作(主要就难在这里)
当前元素入栈给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
只有凹陷的地方才能接到雨水，那么高度一定是先减后增，那我们可以维护一个高度递减的单调栈,这样右边进来一个大的就会形成一个凹槽
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
# 两个数不构成凹槽
if n < 3:
return 0
stack = []
res = 0
for i in range(n):
# 栈不空且栈顶高度小于当前值，需要出栈计算
while stack and height[stack[-1]] < height[i]:
tmp = stack.pop()
# 栈空了直接下一步
if not stack:
break
# 计算高度：弹出那个是最小的，所以要找左右的最小，然后减去弹出的（底部）
h = min(height[i],height[stack[-1]])-height[tmp]
# 计算宽度
w = i - stack[-1] - 1
res += w * h
stack.append(i)
return res给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
我们直接遍历数组，每根柱子X都去找左边小于他的柱子L，右边小于他的柱子R，这样面积就为X*(R-L-1),但这样是$O(n^2)$的时间复杂度；
而在找这个左右边界的时候，我们可以维护一个递增的单调栈，这样就可以在$O(1)$时间复杂度找到边界，进而整个算法时间复杂度为$O(n)$
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
#两边都加0主要是处理边界问题，因为结果有可能在边界产生
heights = [0] + heights + [0]
res = 0
# 我们需要寻找宽度，和高度，而宽度可以由下标相减得到
# 高度也可以由下标得到
# 所以栈中存的是高度的下标
for i in range(len(heights)):
#栈不空且栈顶元素的高度大于当前高度，要出栈计算面积
while stack and heights[stack[-1]] > heights[i]:
tmp = stack.pop()
res = max(res, (i - stack[-1] - 1) * heights[tmp])
# 当前元素入栈
stack.append(i)
return res给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
先用一个字典记录每个字母出现的次数，然后维护一个递增的单调栈
class Solution:
def removeDuplicateLetters(self, s) -> int:
stack = []
seen = set()
remain_counter = collections.Counter(s)
for c in s:
if c not in seen:
while stack and c < stack[-1] and remain_counter[stack[-1]] > 0:
seen.discard(stack.pop())
seen.add(c)
stack.append(c)
remain_counter[c] -= 1
return ''.join(stack)给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
有点难。。。。。
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。
维护一个单调递增的单调栈，当前元素比栈中元素小的时候，移除栈顶元素
class Solution(object):
def removeKdigits(self, num, k):
stack = []
for digit in num:
while k and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
return ''.join(stack[:len(num) - k).lstrip('0') or '0'给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1
维护一个递减的单调栈，当前元素比栈中元素大的时候，弹出栈中小的元素并放入结果(hashmap)中
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack = []
hashmap = {}
for x in nums2:
while stack and stack[-1]<x:
hashmap[stack.pop()] = x
stack.append(x)
return [hashmap.get(x,-1) for x in nums1]给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
这题和上一题不同是他是一个循环数组那我们把这个数组复制一遍
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
stack = []
n = len(nums)
res = [-1] * n
nums = nums * 2
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i]:
res[stack.pop()] = nums[i]
# 这里注意一下我们只要求数组的前一半就行了，所以判断一下
if i < n:
stack.append(i)
return res给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。
输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
从左到右遍历，维护一个单调递增的单调栈，遇到比栈顶小的就出栈，以此来找到左边界 同理，从右往左遍历，维护一个单调递减的单调栈，遇到比栈顶大的就出栈，以此来找到右边界
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
stack = []
n = len(nums)
res = 0
left,right = n,0
for i in range(n):
while stack and nums[stack[-1]] > nums[i]:
left = min(left,stack.pop())
stack.append(i)
stack = []
for i in range(n-1,-1,-1):
while stack and nums[stack[-1]] < nums[i]:
right = max(right,stack.pop())
stack.append(i)
return right - left + 1 if right > left else 0根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
和上题差不多维护一个递减的单调栈，只不过这题要求相隔多少天，栈中存入下标(两个下标相减就能求出距离了)
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
n = len(T)
res = [0] * n
stack = []
for i in range(n):
while stack and T[stack[-1]]<T[i]:
tmp = stack.pop()
res[tmp] = i - tmp
stack.append(i)
return res编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。 今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
题目意思是求之前有多少个小于自己的，我们维护一个递减的单调栈(每个价格，和价格的跨度)就可以了，每次价格大于等于栈顶元素，哪就加上栈顶元素的跨度
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
res = 1
while self.stack and self.stack[-1][0] <= price:
res += self.stack.pop()[1]
self.stack.append((price,res))
return res