行业知识
【算法】贡献法相关题目练习
文章目录
- 贡献法介绍
- 前置知识:单调栈
- 例题——496. 下一个更大元素 I
- 贡献法相关题目
- 2104. 子数组范围和
- 思路
- 代码1——自己写的代码
- 代码2——最小值的贡献和最大值的贡献的关系
- 907. 子数组的最小值之和
- 代码1——单调栈+计算贡献
- 代码2——寻找左右最小值的同时计算答案
- 1856. 子数组最小乘积的最大值
- 2681. 英雄的力量
- 2281. 巫师的总力量和
- ���关链接
本文介绍一些 使用 贡献法 的算法题目。
贡献法介绍
就是计算每个元素对最终答案的贡献是多少,在枚举的过程中加起来。(在枚举之前通常会使用单调栈找到左右第一个比当前元素更大或更小的元素所在的位置)
所以这类题目的关键是想到如何在枚举的过程中计算各个元素的贡献。
前置知识:单调栈
所谓单调栈就是栈里面的数字是单调递增或单调递减的,可以用来确定某个数字前一个或后一个更小或更大的数字。
例题——496. 下一个更大元素 I
496. 下一个更大元素 I
nums1 中每个元素都会在 nums2 中出现,
只需要枚举 nums2 ,在枚举的过程中使用单调栈找到第一个更大的元素,使用哈希表记录下来。
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] ans = new int[nums1.length]; Deque stk = new ArrayDeque(); // 递减的单调队列 Map m = new HashMap(); // 存放每个数字下一个更大的数字 for (int i = 0; i stk.peek()) { // 一个数被弹出来的时候,说明它遇到了第一个比它大的元素 m.put(stk.pop(), nums2[i]); } stk.push(nums2[i]); } for (int i = 0; i贡献法相关题目
2104. 子数组范围和
2104. 子数组范围和
思路
分别计算出每个元素作为最大值的子数组数量和作为最小值的子数组数量,那么这个元素对最终答案的贡献就是 x * (a - b) ,其中 x = nums[i],a 和 b 分别是最大值的子数组数量和作为最小值的子数组数量。(因为题目求的是子数组中最大元素和最小元素的差值,所以作为最大元素时前面是加号,作为最小元素时前面是减号。
Q:如何求当前元素作为最大值时的子数组数量?
A:找到当前元素左右两边第一个大于当前元素的元素位置,假设当前元素下标为 i ,左右两边第一个大于当前元素的下标分别为 x 和 y ,那么子数组的数量就是 (i - x) * (y - i)。(看不懂就看下图)
代码1——自己写的代码
使用两个单调栈,分别求出每个数字左右两侧第一个大于或小于该元素的值。
为了避免重复计算,可以看出每个数字找到的一侧为严格大于或小于,另一侧为大于等于或小于等于。
class Solution { public long subArrayRanges(int[] nums) { int n = nums.length; // 分别计算每个数字作为最大元素的贡献和最小元素的贡献,最大元素贡献之和减去最小元素贡献之和即为最终答案 // Deque stk1 = new ArrayDeque(), stk2 = new ArrayDeque(); int[] rightLarge = new int[n + 1], leftLarge = new int[n + 1]; int[] rightSmall = new int[n + 1], leftSmall = new int[n + 1]; // 初始左右两边为 -1 和 n。 Arrays.fill(rightLarge, n); Arrays.fill(rightSmall, n); Arrays.fill(leftLarge, -1); Arrays.fill(leftSmall, -1); for (int i = 0; i = nums[stk1.peek()]) { int x = stk1.pop(); rightLarge[x] = i; // 右侧大于等于 } if (!stk1.isEmpty()) leftLarge[i] = stk1.peek(); // 左侧严格大于 stk1.push(i); while (!stk2.isEmpty() && nums[i] int x = stk2.pop(); rightSmall[x] = i; // 右侧小于等于 } if (!stk2.isEmpty()) leftSmall[i] = stk2.peek(); // 左侧严格小于 stk2.push(i); } long ans = 0; for (int i = 0; i = nums[stk.peek()]) { right[stk.pop()] = i; // 右侧第一个大于等于的 } if (!stk.isEmpty()) left[i] = stk.peek(); // 左侧第一个严格大于的 stk.push(i); } long ans = 0; for (int i = 0; iQ:为什么所有元素取反后算的就是最小值的贡献?
A:举例 1 2 3,取反后成为 -1 -2 -3,正好原本想找的最小值变成了最大值(它会被找到),同时前面的符号也发生了变化(它会被正确计算)。
907. 子数组的最小值之和
907. 子数组的最小值之和
这道题目是比 2104. 子数组范围和 要简单的,只需要计算每个元素作为最小值时的贡献就好了。
代码1——单调栈+计算贡献
class Solution { private static final int MOD = (int)1e9 + 7; public int sumSubarrayMins(int[] arr) { long ans = 0; // 使用long总归是有利于避免溢出 int n = arr.length; // 计算每个数字作为最小值的贡献,即找到左右两侧第一个小于它的(一边严格小于,另一边小于等于) Deque stk = new ArrayDeque(); int[] right = new int[n], left = new int[n]; Arrays.fill(left, -1); Arrays.fill(right, n); for (int i = 0; i
下一篇:电脑如何清理缓存键?