leetcode 907
来源：1-1 哈希表基础
weixin_慕圣6334738
2022-02-02 08:05:30
波波老师你好, 907题我找到一个这样的代码, 我看跟您的题库也比较相近, 不过我没有太明白的是
res = (res + (long)A[j] * (i - j) * (j - k)) % mod;
这句代码,
(long)A[j] * (i - j) * (j - k)
这个计算背后的逻辑是什么, 为什么他就把每个array最小的加在一起了
相关代码：
public int sumSubarrayMins(int[] A) {
Stack<Integer> s = new Stack<>(); int n = A.length, j, k; long res = 0, mod = (long)1e9 + 7; for (int i = 0; i <= n; i++) { while (!s.isEmpty() && A[s.peek()] > (i == n ? 0 : A[i])) {
j = s.pop();
k = s.isEmpty() ? -1 : s.peek();
res = (res + (long)A[j] * (i - j) * (j - k)) % mod;
}
s.push(i);
} return (int)res;
}非常感谢您的解答!
1回答
-
liuyubobobo
2022-02-02
在运行
res = (res + (long)A[j] * (i - j) * (j - k)) % mod;
这句话的时候，A[j] 是区间 [k, i] 的最小值（j 在 [k, i] 之间。）。[k, i] 之间有多少个区间包含 A[j]，A[j] 就会在最终的结果中出现多少次。
[k, i] 之间包含 j 的区间个数是，对 j 这个位置向左边拓展，最多拓展到 k；向右边拓展，最多拓展到 i。左边拓展有 (j - k) 种可能，右边拓展有 (i - j) 种可能，所以一共有 (i - j) * (j - k) 个区间的最小值是 A[j]。
==========
这个问题的核心其实是：
为什么在运行
res = (res + (long)A[j] * (i - j) * (j - k)) % mod;
的时候，A[j] 是区间 [k, i] 的最小值？
（如果你理解这个原因，下面可以不看了。）
这里用到的是单调栈。单调栈是栈的一个应用，讲清楚单调栈还是挺麻烦的，不是一两句话能讲清楚的，一般在面试中（尤其是国内的面试中）基本也不会考。我强烈建议根据这个问题看这个题解，来理解单调栈。这篇文章是我见过的讲单调栈最清楚的文章（这个题解的作者也是我的课程学生：））
只不过这个问题是动态求解区间的最大值，你问的 907 号问题是求最小值而已，他们背后偶的思想是一样的。
P.S. 84 号问题是 hard，907 号问题是 medium，是不合理的。在我看来，907 可能要比 84 还难一些，至少是一个难度级别。所以力扣的难度分级是不合理的。看看就好。
继续加油！：）
0h022-02-22
相似问题