[LeetCode]Sum of Subarray Minimums

这道题N^2的方法很好想，对于每一个以A[i]结尾的子数组，我们往左扫遍历每一个子数组的最小值即可。但如果用另外一种思路，我们可以统计对于A[i]来说，其左边到哪为止，右边到哪为止，A[i]都是这个范围的最小值。假设从i开始向左走到left，向右走到right，A[i]都是这个范围内的最小值，那么我们有(i - left + 1) * (right - i + 1)个子数组都有A[i]为最小值，左边界有i - left + 1种可能，右边界有right - i + 1种可能。那么我们需要注意的是如何处理相等的数，我们有两种思路：

1. 碰到相等的数的时候停止
2. 碰到相等的数的时候继续，直到碰到小于它的数

但实际上这两种方法都有问题，比如数组[8, 5, 10, 5, 9]：

• 如果用第一种思路，第一个5的左边界为0，右边界为2。第二个5的左边界为2，右边界为4。这样我们会漏统计横跨两个5的区间，比如[0, 4]。
• 如果用第二种思路，第一个5的左边界为0，右边界为4。第二个5的左边界为0，右边界为4。这样很显然我们重复统计了某些区间。

解决这个问题的方法，就是一边用思路1，另一边用思路2。比如我们左边界用思路1，右边界用思路2：

• 第一个5的左边界为0，右边界为4。第二个5的左边界为2，右边界为4。这样我们不会漏掉或者重复统计任何区间。

统计左右边界的时候我们用stack维护单调序列的思路即可。时间复杂度O(N)，代码如下：