文章目录
- 1. 单调栈
- 1.1 理解单调栈（模板）
- 1.2 每日温度
- 1.3 子数组的最小值之和
- 1.4 柱状图中最大的矩形
- 1.5 最大矩形
- 1.6 最大宽度坡
- 1.7 去除重复字母
1. 单调栈
单调栈经典的用法：
对每个位置都求：
- 当前位置的左侧比当前位置的数小，且距离最近的位置
- 当前位置的右侧比当前位置的数小，且距离最近的位置
或者：
- 当前位置的左侧比当前位置的数大，且距离最近的位置
- 当前位置的右侧比当前位置的数大，且距离最近的位置
1.1 理解单调栈（模板）
- 题目分析
单调栈顾名思义就是用栈来维护单调性。栈中存放的是数组元素的下标
在本题思路：
- 遍历nums数组，将数组元素按从小到大的顺序入栈
- 若当前数组元素比栈顶元素小，则弹出栈顶元素，直到栈空或者栈顶元素小于当前元素为止
如何记录距离某个元素左边最近且小与它的数的下标、右边最近且小于它的数的下标：
- 在弹栈的时候，弹出元素就是目标元素
- 小于目标元素、左边最近的元素就是弹出它后的栈顶元素，若栈为空，则为-1
- 大于目标元素、右边最近的元素就是当前还未入栈的那个元素（迫使目标元素出栈的那个元素）
- 当遍历到nums数组末位的时候，如果栈内还有元素，则依次弹出，右边最近且小于它的数没有，为-1，左边就是弹出它后的栈顶元素，若栈空，则为-1
若nums数组中有值相同的元素，那么会有一种情况：
- 假如将要入栈的元素的值等于栈顶元素的值，将栈顶元素弹出
- 弹出后的目标元素的右边最近且小于它的数就是将要入栈的数（当然这只是暂时性的）
- 记cur为目标元素，left为cur左边最近且小于cur的数，right同理。
- 遍历完nums数组后，再从后向前遍历，找nums[cur] == nums[right]
- 将cur的right重新赋值为right的right
- 代码实现
from collections import deque
def foundMonotoneStack(nums):
n = len(nums)
# 需要返回的二维数组
ans = [[] for _ in range(n)]
# 初始化栈
s = deque()
# 存入nums第一个元素的下标
s.append(0)
# 开始遍历数组
for i in range(1, n):
# 如果将要入栈的元素大于栈顶元素就入栈
if nums[s[-1]] < nums[i]:
s.append(i)
continue
# 如果将要入栈的元素小于等于栈顶元素，就挨着弹栈，直到栈空或者将要入栈的元素大于栈顶元素
# 并在弹栈的过程中填入cur的left和right
while len(s) > 0 and nums[s[-1]] >= nums[i]:
cur = s.pop()
if len(s) > 0:
ans[cur].append(s[-1])
else:
ans[cur].append(-1)
ans[cur].append(i)
# 最后记得将 将要入栈的元素 压栈
s.append(i)
# 遍历完数组后检查栈是否为空，不为空又继续弹，规则跟上面那个弹栈差不多
while len(s) > 0:
cur = s.pop()
if len(s) > 0:
ans[cur].append(s[-1])
else:
ans[cur].append(-1)
ans[cur].append(-1)
# 最后再检查nums[cur]是否等于nums[right]，若等于，nums[right]就应该等于right的right
for i in range(n - 1, -1, -1):
if ans[i][1] != -1 and nums[i] == nums[ans[i][1]]:
ans[i][1] = ans[ans[i][1]][1]
return ans
1.2 每日温度
- 题目分析：
在当前位置，想要观察比当前温度更高的气温，需要等待的天数->
在当前位置，想要在右侧找到比当前位置的数更大的数，且距离最近，求这个距离
这样就转换成了类似于模板的题目，只不过栈内元素是从大到小入栈
- 模板代码实现
from collections import deque
def dailyTemperatures(temperatures):
"""
:type temperatures: List[int]
:rtype: List[int]
"""
n = len(temperatures)
ans = [0] * n
# 初始化栈
s = deque()
s.append(0)
for i in range(1, n):
# 如果将要入栈的元素的值小于栈顶元素的值，就入栈
if temperatures[i] < temperatures[s[-1]]:
s.append(i)
continue
# 如果将要入栈的元素的值大于等于栈顶元素的值，就不断弹出栈顶元素
while len(s) > 0 and temperatures[i] >= temperatures[s[-1]]:
cur = s.pop()
# 这里只用考虑右边，所以简洁一些
ans[cur] = i - cur
s.append(i)
# 当遍历完数组后，后面一定没有比栈顶元素大的数了
while len(s) > 0:
cur = s.pop()
ans[cur] = 0
# 最后这里有点难想，我也是因为测试用例不通过，进而调试改进的，测试用例是下面这个
# [34,80,80,34,34,80,80,80,80,34]
for i in range(n - 1, -1, -1):
if ans[i] != 0 and temperatures[i] == temperatures[i + ans[i]]:
if ans[i + ans[i]] == 0:
ans[i] = ans[i + ans[i]]
else:
ans[i] += ans[i + ans[i]]
return ans
- 模板代码改进
# 改进的地方就是，针对这个题而言，当栈顶元素等于将要入栈的元素时，入栈元素照常入栈，没有影响
# 这样也少了最下面那一个稍微难想的循环
from collections import deque
def dailyTemperatures(temperatures):
"""
:type temperatures: List[int]
:rtype: List[int]
"""
n = len(temperatures)
ans = [0] * n
# 初始化栈
s = deque()
s.append(0)
for i in range(1, n):
# 如果将要入栈的元素的值小于栈顶元素的值，就入栈
if temperatures[i] <= temperatures[s[-1]]:
s.append(i)
continue
# 如果将要入栈的元素的值大于等于栈顶元素的值，就不断弹出栈顶元素
while len(s) > 0 and temperatures[i] > temperatures[s[-1]]:
cur = s.pop()
# 这里只用考虑右边，所以简洁一些
ans[cur] = i - cur
s.append(i)
# 当遍历完数组后，后面一定没有比栈顶元素大的数了
while len(s) > 0:
cur = s.pop()
ans[cur] = 0
return ans
1.3 子数组的最小值之和
- 题目思路
一般思路：找出所有的连续子数组，然后再求出每个子数组中的最小值进行累加
如何利用单调栈的特性来做？
- 一个最小值可能在多个子数组中出现
- 在单调栈的模板中，我们有cur、left和right。
* left表示在cur的左边、距离cur最近且小于cur的数的下标
* right表示在cur的右边、距离cur最近且小于cur的数的下标
- 那么在left到cur之间、cur到right之间的数一定是比cur大的数
- 由这些数组成的连续子数组且包含cur，它们的最小值一定是cur位置的数，所以我们的目的就变成了计算这些数组的数目
- 那么如何计算这些数组的数量呢？
* 假如给定一系列下标：[left, a, b, c, cur, d, e, f, g, right]
* 那么符合条件的子数组有：
1. [a, b, c, cur]
2. [a, b, c, cur, d]
3. [a, b, c, cur, d, e]
4. [a, b, c, cur, d, e, f]
5. [a, b, c, cur, d, e, f, g]
6. [b, c, cur]
7. [b, c, cur, d]
8. [b, c, cur, d, e]
9. [b, c, cur, d, e, f]
10.[b, c, cur, d, e, f, g]
11.[c, cur]
12.[c, cur, d]
13.[c, cur, d, e]
14.[c, cur, d, e, f]
15.[c, cur, d, e, f, g]
16.[cur]
17.[cur, d]
18.[cur, d, e]
19.[cur, d, e, f]
20.[cur, d, e, f, g]
一共二十个
* 可以看到由a开头的数组5个，b开头的5个，c开头的5个，cur开头的5个，一共是由left到cur中间的数包括cur来开头的，像这种由哪个开头的这类数组一共有cur-left种
* 又可以看到由cur结尾的数组4个，d结尾的4个，e结尾的4个，f结尾的4个，g结尾的4个，一共是由cur到right中间的数包括cur来结尾的，像这种由哪个结尾的这类数组一共有right-cur种
* 所以总共就有(cur-left)*(right-cur)种数组
- 当将要入栈的元素的值等于栈顶元素的时候怎么办？
* 找个特例自己看哪种合适
* 本题中，照常弹栈即可
- 代码实现
# 还是照常套模板
from collections import deque
def sumSubarrayMins(arr):
"""
:type arr: List[int]
:rtype: int
"""
MAX = 10 ** 9 + 7
n = len(arr)
all = 0
s = deque()
s.append(0)
# 大压小
for i in range(1, n):
if arr[i] > arr[s[-1]]:
s.append(i)
continue
while len(s) > 0 and arr[i] <= arr[s[-1]]:
cur = s.pop()
if len(s) > 0:
left = s[-1]
else:
# 如果栈内没元素，就表示cur的左边没有比它小的数了，此时cur-left=cur-(-1)，是因为要包括0在内
left = -1
right = i
# 同余原理
all += (all + (cur - left) * (right - cur) * arr[cur]) % MAX
s.append(i)
while len(s) > 0:
cur = s.pop()
# 最后执行弹栈操作时，它们没有right，表示右边没有比它们小的数了，right-cur=n-cur，这也是因为需要将n-1包括进去
right = n
if len(s) > 0:
left = s[-1]
else:
left = -1
all += (all + (cur - left) * (right - cur) * arr[cur]) % MAX
return all
1.4 柱状图中最大的矩形
- 题目思路
跟上个题的思路差不多
找到cur的left和right：
- cur：当前弹出栈的元素的下标
- left：cur左边、距离cur最近且比cur小的数的下标
- right：cur右边、距离cur最近且比cur小的数的下标
每个cur的最大面积：(right-left-1) * heights[cur]
- 代码实现
from collections import deque
def largestRectangleArea(heights):
"""
:type heights: List[int]
:rtype: int
"""
max_area = 0
n = len(heights)
s = deque()
s.append(0)
for i in range(1, n):
if heights[i] > heights[s[-1]]:
s.append(i)
continue
while len(s) > 0 and heights[i] <= heights[s[-1]]:
cur = s.pop()
left = s[-1] if len(s) > 0 else -1
right = i
max_area = max(max_area, (right - left - 1) * heights[cur])
s.append(i)
while len(s) > 0:
cur = s.pop()
left = s[-1] if len(s) > 0 else -1
right = n
max_area = max(max_area, (right - left - 1) * heights[cur])
return max_area
1.5 最大矩形
- 题目分析
解决方法：转换为柱状图的解决思路
首先，以上图为例：
以第一行为底，柱状图的大小为[1,0,1,0,0]
以第二行为底，柱状图的大小为[2,0,2,1,1]
以第三行为底，柱状图的大小为[3,1,3,2,2]
以第四行为底，柱状图的大小为[4,0,0,1,0]
循环三次，在每次循环中找最大的矩形面积即可
- 代码实现
from collections import deque
def maximalRectangle(matrix):
"""
:type matrix: List[str]
:rtype: int
"""
# 将matrix中的每个字符串变成一个整型列表
matrix = [list(map(int, list(matrix[i]))) for i in range(len(matrix))]
if len(matrix) == 0:
return 0
n = len(matrix)
m = len(matrix[0])
max_area = 0
# 用来更新柱状图的信息
temp_arr = [0] * m
for i in range(n):
# 下面的循环就跟前面柱状图那个题的代码一样
# 需要注意的是不要把i和j搞混了
for j in range(m):
temp_arr[j] = 0 if matrix[i][j] == 0 else (temp_arr[j] + matrix[i][j])
s = deque()
s.append(0)
for j in range(1, m):
if temp_arr[j] > temp_arr[s[-1]]:
s.append(j)
continue
while len(s) > 0 and temp_arr[j] <= temp_arr[s[-1]]:
cur = s.pop()
left = s[-1] if len(s) > 0 else -1
right = j
max_area = max(max_area, (right - left - 1) * temp_arr[cur])
s.append(j)
while len(s) > 0:
cur = s.pop()
left = s[-1] if len(s) > 0 else -1
right = m
max_area = max(max_area, (right - left - 1) * temp_arr[cur])
return max_area
1.6 最大宽度坡
- 题目思路
要求的是什么？
求的是一段距离（也就是下标之差）
cur的右边、距离cur最远、比cur大的数的下标
cur的左边、距离cur最远、比cur小的数的下标
单调栈压栈方式：小压大，比栈顶元素小的进栈，如果比栈顶元素大，就不用进栈，继续比较下一个。
如果比栈顶元素大的进栈了，那么后续遇到比这个栈顶元素大的，所形成的最大宽度坡一定比它下面那个元素所形成的最大宽度坡小。
因为它下面的那个本身值也比栈顶的小，并且位置也比栈顶的靠前
一轮比较完后，栈内的元素从底到顶就是按照从大到小的顺序。
然后再从尾到头遍历数组A，如果A[i]大于等于栈顶元素，就弹出栈顶元素，记录当前的宽度坡（始终记录最大的宽度坡）；如果A[i]小于栈顶元素，就往前遍历A数组。
- 代码实现
from collections import deque
def maxWidthRamp(nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
max_slope = 0
s = deque()
s.append(0)
for i in range(1, n):
if nums[i] < nums[s[-1]]:
s.append(i)
continue
for i in range(n - 1, -1, -1):
while len(s) > 0 and nums[s[-1]] <= nums[i]:
max_slope = max(max_slope, i - s.pop())
return max_slope
1.7 去除重复字母
- 题目分析
首先，字符的顺序不能更改
对于前面的字符，我们只需要统计一下它们的总出现次数，只要大于0，就能删除
如何用单调栈来做呢？
- 压栈的时候大压小，如果当前字符大于栈顶字符、且栈内没有该元素，压栈
- 如果当前字符小于等于栈顶字符，判断栈顶字符出现的次数是否大于0，若大于就可以弹出，若小于0就不能弹出
- 每一次压栈后，将这个字符的出现次数-1，并且将其标记为True，表示栈里面有这个元素
- 每一次弹栈后，将这个字符标记为False，表示栈里没有这个元素了
- 下面的代码有点绕，也是自己测试了好久写出来的
from collections import deque
def removeDuplicateLetters(s):
"""
:type s: str
:rtype: str
"""
n = len(s)
cnts = [0] * 26
for i in range(n):
cnts[ord(s[i]) - ord('a')] += 1
marked = [False] * 26
# 初始化栈
stack = deque()
stack.append(s[0])
cnts[ord(s[0]) - ord('a')] -= 1
marked[ord(s[0]) - ord('a')] = True
for i in range(1, n):
# 比栈顶字符大、且没在栈内出现过，入栈
if marked[ord(s[i]) - ord('a')] == False and s[i] > stack[-1]:
stack.append(s[i])
marked[ord(s[i]) - ord('a')] = True
cnts[ord(s[i]) - ord('a')] -= 1
continue
# 栈不为空、当前字符小于等于栈顶字符、栈顶元素剩余出现次数大于0、且当前字符未在栈内出现，弹栈
while len(stack) > 0 and s[i] <= stack[-1] and cnts[ord(stack[-1]) - ord('a')] > 0 and marked[ord(s[i]) - ord('a')] == False:
marked[ord(stack[-1]) - ord('a')] = False
stack.pop()
# 如果当前字符连上面两个条件都不满足，但是它没在栈内出现过，入栈
if marked[ord(s[i]) - ord('a')] == False:
stack.append(s[i])
marked[ord(s[i]) - ord('a')] = True
# 如果在栈内出现过，就跳过这个字符，并且出现次数减一
cnts[ord(s[i]) - ord('a')] -= 1
# 将栈内字符拼接成一个字符串
ans = [''] * len(stack)
for i in range(len(ans) - 1, -1, -1):
ans[i] = stack.pop()
return ''.join(ans)
- 精简版
from collections import deque
def removeDuplicateLetters(s):
"""
:type s: str
:rtype: str
"""
n = len(s)
cnts = [0] * 26
for i in range(n):
cnts[ord(s[i]) - ord('a')] += 1
marked = [False] * 26
# 初始化栈
stack = deque()
stack.append(s[0])
cnts[ord(s[0]) - ord('a')] -= 1
marked[ord(s[0]) - ord('a')] = True
for i in range(1, n):
# 如果当前字符没在栈内出现
if marked[ord(s[i]) - ord('a')] == False:
# 如果栈内有字符、当前字符小于等于栈顶字符、且栈顶字符剩余出现次数大于0
while len(stack) > 0 and s[i] <= stack[-1] and cnts[ord(stack[-1]) - ord('a')] > 0:
marked[ord(stack[-1]) - ord('a')] = False
stack.pop()
# 如果栈空、当前字符大于栈顶字符、栈顶字符剩余出现次数等于0，就直接入栈
stack.append(s[i])
marked[ord(s[i]) - ord('a')] = True
# 不管它入不入栈，它的剩余出现次数都要减1
cnts[ord(s[i]) - ord('a')] -= 1
# 将栈内字符拼接成一个字符串
ans = [''] * len(stack)
for i in range(len(ans) - 1, -1, -1):
ans[i] = stack.pop()
return ''.join(ans)
