1回答

liuyubobobo

2018-09-17

已采纳

以下简要说明基于我的代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0907-Sum-of-Subarray-Minimums/cpp-0907/main.cpp

计算对于每一个A[i]，有多少子集，其最小值是自己。

针对每一个A[i]，求出比i大的最小索引j1，使得A[j1] <= A[i]；

针对每一个A[i]，求出比i小的最大索引j2，使得A[j2] < A[i]；

则在子集[a, b]中，a可以取 j2 + 1 到 i 的任何值；b可以取 i 到 j1 + 1 的任何值，使得[a,b]这个子集的最小值都为A[i]。

这样的子集有 (i - j2) * (j1 - i) 个。

我们可以遍历一遍整个A，对每个A[i]，直接计算出 (i - j2) * (j1 - i) * A[i]，把他们加起来就好了。

==========

下面的关键是，如何高效的针对每一个A[i]，求出比i大的最小索引j1，使得A[j1] <= A[i]；以及针对每一个A[i]，求出比i小的最大索引j2，使得A[j2] < A[i]。

这是一个经典的使用栈解决的问题。我建议看一遍901号问题。完全是这个子问题。https://leetcode.com/problems/online-stock-span/description/

（只不过这个问题是找到最靠近当前点的，比当前点还要大的数字的位置。）

经典的42题，也可以使用类似的思路解决：https://leetcode.com/problems/trapping-rain-water/description/

我不太有信心用比较简短的语言把这个思路阐述出来。整体我们在栈中维护了一个当前所能寻找的递增序列（也可能是递减序列，根据题意来定），每当有一个新元素来临，一旦这个元素比栈顶元素小（也可能是大，根据题意来定），我们就解决了栈顶元素的问题。以此类推。

如果对这个问题不熟悉，我建议以901号问题为例，先自己用最朴素的思想写出一个解，然后对于提交产生的错误用例，仔细理解自己的算法为什么不work，再仔细跟一遍答案代码的逻辑。体会一下答案代码为什么work。这个过程可能要重复几轮，才能比较透彻的彻底理解这个算法。（我的901号问题参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0901-Online-Stock-Span/cpp-0901/main.cpp）

加油！：）

1

3

慕雪9091725

非常感谢！

2018-09-17

共3条回复