题单来源

https://leetcode.cn/problems/beautiful-towers-ii/solutions/2456562/qian-hou-zhui-fen-jie-dan-diao-zhan-pyth-1exe/

经典题单

496. 下一个更大元素 I（单调栈模板题）

https://leetcode.cn/problems/next-greater-element-i/description/

提示：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

预先处理出 nums2 数组中每个数字的下一个更大数字，存储在哈希表中。
生成 ans 数组时，从哈希表中逐个取结果即可。

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int n = nums1.length;Map<Integer, Integer> m = new HashMap<>();Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < nums2.length; ++i) {while (!stk.isEmpty() && nums2[i] > stk.peek()) m.put(stk.pop(), nums2[i]);stk.push(nums2[i]);}int[] ans = new int[n];for (int i = 0; i < n; ++i) {ans[i] = m.getOrDefault(nums1[i], -1);}return ans;}
}

503. 下一个更大元素 II（单调栈+循环数组）

https://leetcode.cn/problems/next-greater-element-ii/description/

class Solution {public int[] nextGreaterElements(int[] nums) {int n = nums.length;int[] ans = new int[n];Arrays.fill(ans, -1);Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < 2 * n - 1; ++i) {int id = i % n;while (!stk.isEmpty() && nums[id] > nums[stk.peek()]) ans[stk.pop()] = nums[id];stk.push(id);}return ans;}
}

2454. 下一个更大元素 IV（第二个更大的元素：两个单调栈）

https://leetcode.cn/problems/next-greater-element-iv/description/

提示：
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

用两个单调栈来分别处理第一个和第二个更大，当第一次被弹出时，说明遇到了第一个更大的元素，将其弹出后放入第二个单调栈中。

在第二个单调栈被弹出的元素说明遇到了第二个更大的元素。

class Solution {public int[] secondGreaterElement(int[] nums) {int n= nums.length;int[] ans = new int[n];Arrays.fill(ans, -1);Deque<Integer> stk = new ArrayDeque<>(), stk2 = new ArrayDeque<>();for (int i = 0; i < n; ++i) {// 处理第二个单调栈while (!stk2.isEmpty() && nums[i] > nums[stk2.peek()]) {ans[stk2.pop()] = nums[i];}// 处理第一个单调栈List<Integer> ls = new ArrayList<>();while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {ls.add(stk.pop());}for (int j = ls.size() - 1; j >= 0; --j) stk2.push(ls.get(j));stk.push(i);}return ans;}
}

456. 132 模式（单调栈找上一个更大元素+哈希表记录最小值）

https://leetcode.cn/problems/132-pattern/description/

枚举的x作为最后一个数字，当找到上一个更大的数字时，考虑其之前出现的最小值是否小于当前值即可。

class Solution {public boolean find132pattern(int[] nums) {// 找上一个更大元素，并检查当前是否大于更大元素之前出现过的最小值int mn = Integer.MAX_VALUE;     // 记录已经枚举过的数值中的最小值Deque<Integer> stk = new ArrayDeque<>();Map<Integer, Integer> m = new HashMap<>();  // 记录各个数值之前出现的最小值for (int x: nums) {m.put(x, mn);while (!stk.isEmpty() && x >= stk.peek()) {stk.pop();}if (!stk.isEmpty() && x > m.get(stk.peek())) return true;stk.push(x);if (x < mn) mn = x;}return false;}
}

739. 每日温度

https://leetcode.cn/problems/daily-temperatures/description/

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] ans = new int[n];Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < n; ++i) {// 维护单调递减的单调栈while (!stk.isEmpty() && temperatures[i] > temperatures[stk.peek()]) {// 当元素被弹出时，说明遇到了更大的值ans[stk.peek()] = i - stk.pop();}stk.push(i);}return ans;}
}

901. 股票价格跨度

https://leetcode.cn/problems/online-stock-span/description/

提示：
1 <= price <= 10^5
最多调用 next 方法 10^4 次

class StockSpanner {int t = 0;// 单调递减的单调栈Deque<Integer> stk = new ArrayDeque<>();List<Integer> ls = new ArrayList<>();public StockSpanner() {stk.push(-1);}public int next(int price) {    ls.add(price);while (stk.size() > 1 && price >= ls.get(stk.peek())) {stk.pop();}int res = t - stk.peek();stk.push(t++);return res;}
}/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner obj = new StockSpanner();* int param_1 = obj.next(price);*/

1019. 链表中的下一个更大节点

https://leetcode.cn/problems/next-greater-node-in-linked-list/description/

提示：

链表中节点数为 n
1 <= n <= 10^4
1 <= Node.val <= 10^9

存储列表后，再使用单调栈处理。

class Solution {public int[] nextLargerNodes(ListNode head) {List<Integer> ls = new ArrayList<>();while (head != null) {ls.add(head.val);head = head.next;}int n = ls.size();int[] ans = new int[n];Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < n; ++i) {while (!stk.isEmpty() && ls.get(i) > ls.get(stk.peek())) {ans[stk.pop()] = ls.get(i);}stk.push(i);}return ans;}
}

1124. 表现良好的最长时间段（单调栈解法⭐⭐⭐⭐⭐）

https://leetcode.cn/problems/longest-well-performing-interval/description/

提示：
1 <= hours.length <= 10^4
0 <= hours[i] <= 16

先正序遍历用单调栈处理，再反向遍历利用单调栈中结果。

class Solution {public int longestWPI(int[] hours) {int n = hours.length;int[] s = new int[n + 1];ArrayDeque<Integer> stk = new ArrayDeque<>();stk.push(0);// 单调递减的单调栈for (int i = 1; i <= n; ++i) {s[i] = s[i - 1] + (hours[i - 1] > 8? 1: -1);if (s[i] < s[stk.peek()]) stk.push(i);}int ans = 0;for (int i = n; i > 0; --i) {while (!stk.isEmpty() && s[i] > s[stk.peek()]) {ans = Math.max(ans, i - stk.pop());}}return ans;}
}

1475. 商品折扣后的最终价格（单调栈找下一个更小的元素）

https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/description/

提示：
1 <= prices.length <= 500
1 <= prices[i] <= 10^3

class Solution {public int[] finalPrices(int[] prices) {int n = prices.length;// 单调栈找下一个<=的元素Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < n; ++i) {while (!stk.isEmpty() && prices[i] <= prices[stk.peek()]) {prices[stk.pop()] -= prices[i];}stk.push(i);}return prices;}
}

2289. 使数组按非递减顺序排列⭐⭐⭐⭐⭐

https://leetcode.cn/problems/steps-to-make-array-non-decreasing/description/

提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

解法——等价转换 + 利用单调性🐂

https://leetcode.cn/problems/steps-to-make-array-non-decreasing/solutions/1524614/by-endlesscheng-s2yc/

class Solution {public int totalSteps(int[] nums) {int n = nums.length;// 单调递减 存储元素及其被删除的时刻Deque<int[]> stk = new ArrayDeque<>();int ans = 0;for (int i = 0; i < n; ++i) {int maxT = 0;while (!stk.isEmpty() && nums[i] >= nums[stk.peek()[0]]) {maxT = Math.max(stk.pop()[1], maxT);}if (!stk.isEmpty()) ans = Math.max(ans, maxT + 1);stk.push(new int[]{i, maxT + 1});}return ans;}
}

矩形系列

见：【算法】单调栈题单——矩阵系列

字典序最小

见：【算法】单调栈题单——字典序最小

贡献法

2818. 操作使得分最大（⭐质因数分解+单调栈贡献法+排序贪心）好题！

https://leetcode.cn/problems/apply-operations-to-maximize-score/

提示：
1 <= nums.length == n <= 10^5
1 <= nums[i] <= 10^5
1 <= k <= min(n * (n + 1) / 2, 10^9)

出自周赛：【力扣周赛】第 358 场周赛（大杂烩题目：质因数分解+快速幂+单调栈+贡献法）

class Solution {final long MOD = (long)1e9 + 7;final static int MX = (int)1e5 + 1;static int[] omega = new int[MX];static {for (int i = 2; i < MX; ++i) {if (omega[i] == 0) {    // i 是质数for (int j = i; j < MX; j += i) {omega[j]++;     // i 是 j 的一个质因子}}}}public int maximumScore(List<Integer> nums, int k) {int n = nums.size();int[][] scores = new int[n][2];for (int i = 0; i < n; ++i) {scores[i][0] = op(nums.get(i));         // 求质数分数}Deque<Integer> stk = new ArrayDeque<>();int[] l = new int[n], r = new int[n];       // 存储各个元素对应可以选择的l~r范围Arrays.fill(l, -1);Arrays.fill(r, n);for (int i = 0; i < n; ++i) {while (!stk.isEmpty() && scores[i][0] > scores[stk.peek()][0]) {r[stk.pop()] = i;}if (!stk.isEmpty()) l[i] = stk.peek();stk.push(i);}for (int i = 0; i < n; ++i) {scores[i][0] = nums.get(i);             // 元素的贡献scores[i][1] = (r[i] - i) * (i - l[i]); // 元素可以被选择的次数}// 排序+贪心找 k次操作对应哪些元素Arrays.sort(scores, (x, y) -> y[0] - x[0]);     // 分数倒序排序long ans = 1;for (int i = 0; i < n && k > 0; ++i) {if (scores[i][1] <= k) {ans = (ans * qmi((long)scores[i][0], (long)scores[i][1])) % MOD;} else {ans = (ans * qmi((long)scores[i][0], (long)k)) % MOD;break;}k -= scores[i][1];}return (int)ans;}// 质因数分解 得到不同质因数的数量public int op(int x) {return omega[x];}// 快速幂public long qmi(long a, long b) {long p = MOD;long res = 1 % p, t = a;while (b != 0) {if ((b & 1) == 1) res = res * t % p;t = t * t % p;b >>= 1;}return res;}
}

---

更多题目

更多见：【算法】贡献法相关题目练习