做网站的公司倒闭了,网站美工做图推荐,网站设计职业培训,浙江高端网站建设公司文章目录 题单来源经典题单496. 下一个更大元素 I#xff08;单调栈模板题#xff09;503. 下一个更大元素 II#xff08;单调栈循环数组#xff09;2454. 下一个更大元素 IV#xff08;第二个更大的元素#xff1a;两个单调栈#xff09;456. 132 模式#xff08;单调… 文章目录 题单来源经典题单496. 下一个更大元素 I单调栈模板题503. 下一个更大元素 II单调栈循环数组2454. 下一个更大元素 IV第二个更大的元素两个单调栈456. 132 模式单调栈找上一个更大元素哈希表记录最小值739. 每日温度901. 股票价格跨度1019. 链表中的下一个更大节点1124. 表现良好的最长时间段单调栈解法⭐⭐⭐⭐⭐1475. 商品折扣后的最终价格单调栈找下一个更小的元素2289. 使数组按非递减顺序排列⭐⭐⭐⭐⭐解法——等价转换 利用单调性 矩形系列字典序最小贡献法2818. 操作使得分最大⭐质因数分解单调栈贡献法排序贪心好题更多题目 题单来源
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;MapInteger, Integer m new HashMap();DequeInteger 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);DequeInteger 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);DequeInteger 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];}// 处理第一个单调栈ListInteger 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; // 记录已经枚举过的数值中的最小值DequeInteger stk new ArrayDeque();MapInteger, 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];DequeInteger 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;// 单调递减的单调栈DequeInteger stk new ArrayDeque();ListInteger 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) {ListInteger ls new ArrayList();while (head ! null) {ls.add(head.val);head head.next;}int n ls.size();int[] ans new int[n];DequeInteger 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];ArrayDequeInteger 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;// 单调栈找下一个的元素DequeInteger 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;// 单调递减 存储元素及其被删除的时刻Dequeint[] 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(ListInteger 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)); // 求质数分数}DequeInteger 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;}
}更多题目
更多见【算法】贡献法相关题目练习
