单调栈题目汇总

摘要: 单调栈的题目汇总

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

单调栈基本思想和模板

单调栈的算法原理和代码模板看这篇文章：单调栈。

---

单调栈的题目

以下是单调栈的题目列表，思路类似，可以集中练习。

• 42. 接雨水
• 84. 柱状图中最大的矩形
• 85. 最大矩形
• 221. 最大正方形
• 496. 下一个更大元素 I
• 503. 下一个更大元素 II
• 556. 下一个更大元素 III
• 739. 每日温度
• 901. 股票价格跨度
• 907. 子数组的最小值之和
• 1019. 链表中的下一个更大节点
• 1475. 商品折扣后的最终价格
• 975. 奇偶跳
• 1063. 有效子数组的数目

---

132模式及其应用

以下两题为同一个思路: 第一题为基础，第二题以第一题为组件。参考文章：力扣456-132模式。

• 456. 132模式
• 255. 验证前序遍历序列二叉搜索树 验证前序遍历序列不含231模式
• 946. 验证栈序列 验证弹出序列不含 312 模式
• 剑指 Offer 31. 栈的压入、弹出序列 验证弹出序列不含 312 模式
• 剑指 Offer 33. 二叉搜索树的后序遍历序列 验证后续遍历序列不含 312 模式

---

最大宽度坡及其应用

以下两题为同一个思路: 第一题为基础，第二题以第一题为组件。

• 962. 最大宽度坡

因为对起点i,右侧的 $j1 < j2$, 若 $A[j1] < A[j2]$, 则j1无用,因为对任意i,若j1为候选,则j2总会更好,因此可能的右端点为从右到左单调递增的子序列. 同理可能的 i 是从左到右的单调递减的子序列. 先预处理出两个单调栈的元素: 可能的 i 下标和可能的 j 下标, 然后从右往左枚举 veci, 操作 vecj.

• 1124. 表现良好的最长时间段

1. 先预处理好前缀和数组sums, 所求区间在前缀和数组上的特性与上题相同,可以直接套用.
2. 也可以用哈希表维护,键为前缀和,值为最早出现的索引,关键引理: 当前前缀和为 sum, sum-2 出现的一定不会比sum-1更早.

参考文章：力扣962-最大宽度坡、力扣1124-表现良好的最长时间段。

---

单调栈维护贪心

以下四题均为同一思路(单调栈维护贪心): 当前枚举的元素先作为候选压进栈,该元素最终会不会是结果中的一员。

要看后面枚举的元素会不会通过单调关系以及其它条件将它弹出栈.

• 316. 去除重复字母
• 1081. 不同字符的最小子序列
• 402. 移掉K位数字
• 321. 拼接最大数

参考文章：贪心-删数,拼数,选数,改数、【STL】字典序比较 lexicographical_compare。

---

保存值而不是下标的单调栈

• 768. 最多能完成排序的块 II

参考文章：力扣768-最多能完成排序的块2

---