单调栈用法

文章目录

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 dequedef 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和rightwhile 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的rightfor 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 - curs.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 - curs.append(i)# 当遍历完数组后，后面一定没有比栈顶元素大的数了while len(s) > 0:cur = s.pop()ans[cur] = 0return 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 dequedef sumSubarrayMins(arr):""":type arr: List[int]:rtype: int"""MAX = 10 ** 9 + 7n = len(arr)all = 0s = deque()s.append(0)# 大压小for i in range(1, n):if arr[i] > arr[s[-1]]:s.append(i)continuewhile 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 = -1right = i# 同余原理all += (all + (cur - left) * (right - cur) * arr[cur]) % MAXs.append(i)while len(s) > 0:cur = s.pop()# 最后执行弹栈操作时，它们没有right，表示右边没有比它们小的数了，right-cur=n-cur，这也是因为需要将n-1包括进去right = nif len(s) > 0:left = s[-1]else:left = -1all += (all + (cur - left) * (right - cur) * arr[cur]) % MAXreturn all

1.4 柱状图中最大的矩形

题目思路

跟上个题的思路差不多找到cur的left和right：- cur：当前弹出栈的元素的下标- left：cur左边、距离cur最近且比cur小的数的下标- right：cur右边、距离cur最近且比cur小的数的下标每个cur的最大面积：(right-left-1) * heights[cur]

代码实现

from collections import dequedef largestRectangleArea(heights):""":type heights: List[int]:rtype: int"""max_area = 0n = len(heights)s = deque()s.append(0)for i in range(1, n):if heights[i] > heights[s[-1]]:s.append(i)continuewhile len(s) > 0 and heights[i] <= heights[s[-1]]:cur = s.pop()left = s[-1] if len(s) > 0 else -1right = imax_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 -1right = nmax_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 dequedef 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 0n = len(matrix)m = len(matrix[0])max_area = 0# 用来更新柱状图的信息temp_arr = [0] * mfor 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)continuewhile len(s) > 0 and temp_arr[j] <= temp_arr[s[-1]]:cur = s.pop()left = s[-1] if len(s) > 0 else -1right = jmax_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 -1right = mmax_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 dequedef maxWidthRamp(nums):""":type nums: List[int]:rtype: int"""n = len(nums)max_slope = 0s = deque()s.append(0)for i in range(1, n):if nums[i] < nums[s[-1]]:s.append(i)continuefor 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 dequedef removeDuplicateLetters(s):""":type s: str:rtype: str"""n = len(s)cnts = [0] * 26for i in range(n):cnts[ord(s[i]) - ord('a')] += 1marked = [False] * 26# 初始化栈stack = deque()stack.append(s[0])cnts[ord(s[0]) - ord('a')] -= 1marked[ord(s[0]) - ord('a')] = Truefor 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')] = Truecnts[ord(s[i]) - ord('a')] -= 1continue# 栈不为空、当前字符小于等于栈顶字符、栈顶元素剩余出现次数大于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')] = Falsestack.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 dequedef removeDuplicateLetters(s):""":type s: str:rtype: str"""n = len(s)cnts = [0] * 26for i in range(n):cnts[ord(s[i]) - ord('a')] += 1marked = [False] * 26# 初始化栈stack = deque()stack.append(s[0])cnts[ord(s[0]) - ord('a')] -= 1marked[ord(s[0]) - ord('a')] = Truefor i in range(1, n):# 如果当前字符没在栈内出现if marked[ord(s[i]) - ord('a')] == False:# 如果栈内有字符、当前字符小于等于栈顶字符、且栈顶字符剩余出现次数大于0while len(stack) > 0 and s[i] <= stack[-1] and cnts[ord(stack[-1]) - ord('a')] > 0:marked[ord(stack[-1]) - ord('a')] = Falsestack.pop()# 如果栈空、当前字符大于栈顶字符、栈顶字符剩余出现次数等于0，就直接入栈stack.append(s[i])marked[ord(s[i]) - ord('a')] = True# 不管它入不入栈，它的剩余出现次数都要减1cnts[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)