leetcode-WeeklyContest-102

Question

波波老师，您好：
您一定参加今天上午的周赛了吧，我想问一下关于第三题子数组的最小值之和，当时做的时候用针对每个起点用动态规划的思路去遍历求最小值，算法的时间复杂度为O(N^2)，超时了，下来看了好一会儿别人的代码，还是没看懂，您能给我简单的点拔下这道题的思路吗？谢谢您！

Answer 1

liuyubobobo 2018-09-17 02:49:37

以下简要说明基于我的代码：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）

加油！：）

• 提问者 慕雪9091725 #1

  谢谢bobo老师！：
  之前就是一直在找一个方法看对与每个元素，它能做为最小值辐射到的最大范围，但是自己没有总结到：
  针对每一个A[i]，求出比i大的最小索引j1，使得A[j1] <= A[i]；
  针对每一个A[i]，求出比i小的最大索引j2，使得A[j2] < A[i]；
  这一步，看到这个地方，顿时开朗了。
  
  上周周赛做901题的时候，自己写的思路就是每次存下当前位置的最大长度，如果当前位置小于之前的就记1，如果大于之前的先加上上一个位置的长度，然后继续去与上一个位置存的长度前对应位置做比较
  
  其实感觉和这里用辅助栈的总的思路挺像的，但是用辅助栈的抽象层次要高一些，每次存下了还没有发生变化（也是可能发生变化的位置），省了自己去循环跳转的过程。
  
  现在感觉自己很不稳定，leetcode上做周赛，题型对胃口的时候很较快的做出前三题，最后排名能进前300，有时候做的不顺第二题思路没想清楚都会卡半天，面试也是，做的好的时候很好，做的不好经常卡死，感觉还是得慢慢来，慢慢积累。  : (

• liuyubobobo 回复 提问者 慕雪9091725 #2

  加油！：）

• 提问者 慕雪9091725 #3

  非常感谢！