1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int sumSubarrayMins(int[] arr) {
        int mod = 1000000007;
        int[] newArr = new int[arr.length + 2];
        newArr[0] = Integer.MIN_VALUE;
        for (int i = 1; i <= arr.length; i++) {
            newArr[i] = arr[i - 1];
        }
        newArr[newArr.length - 1] = Integer.MIN_VALUE;
        Deque<Integer> monoStack = new ArrayDeque<>();
        long ans = 0;
        for (int i = 0; i < newArr.length; i++) {
            while (!monoStack.isEmpty() && newArr[i] < newArr[monoStack.peek()]) {
                int currIdx = monoStack.pop();
                ans += 1L * newArr[currIdx] * (i - currIdx) * (currIdx - monoStack.peek());
            }
            monoStack.push(i);
        }
        return (int) (ans % mod);
    }
}

这道题好啊. 就是用单调栈. 一个数字可以做很多subarray中的minimum. 那么如何找到这些subarray呢? 我们看某个数字它右边比它小的数字在哪里, 再看该数字左边比它小的数字在哪里. 我们举个例子:
array: [0, 1, 3, 2, 4, 5, 1, 3, 5, 6, 0, 2, 7]
idx: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
我们来看中间那个1(idx是6). 如果这个1是某个subarray中的minimum, 那么这个1在subarray中肯定有一个位置, 比如是subarray中的第0个位置,第1个位置, 第2位置等等. 假设它是第0个位置, 那么此时subarray就是1打头. 那么这个subarray最长可以是多少呢? 假设最长是x, 那么1打头的且1是其中最小的subarray个数就是x个. 想一想是这个道理吧. 由于1打头, 我们就需要看1右侧比1小的数字的index在哪里. 我们发现是0, 它的idx是10. 那么1打头的满足题意的subarray的最长
长度就是10 - 6 = 4(因为我们不能包括idx 10, idx 10对应的0是小于1的). 这样我们得到的[1], [1, 3], [1, 3, 5], [1, 3, 5, 6]这四个都是1打头满足题意的.

现在考虑如果1是subarray中第1个元素呢? 此时1之前的5就是subarray中的第0个元素. 那么此时有多少种满足题意的subarray呢? 也是4个, 也就是我们刚才讨论的四种把头部各自添上5就行. 也就是[5, 1], [5, 1, 3], [5, 1, 3, 5], [5, 1, 3, 5, 6]

现在考虑如果1是subarray中的第二个元素呢? 此时5之前的4就是subarray中第0个元素, 4之后的5就是第1个元素而1就是第二个元素. 那此时有多少种呢? 还是4种. 也就是把1作为第1个元素的subarray中前面都添上4即可.

以此类推.

那么什么时候这样类推停止呢? 当遇到1之前的某个数字小于1的时候. 我们这个例子中就是遇到idx是0的这个元素也就是0. 此时如果包含它, 1就不再是subarray中最小的了. 于是此时就停止.

我们维护一个non-decreasing subarray. 当我们能pop出一个元素时, 这个被pop出的元素的next smaller就是现在的array[i], 于是以被pop出来的元素
打头的且被pop出的元素是最小的subarray的个数就是i - 被pop出的元素的idx. 好在我们stack中装的都是idx. 假设被pop出的元素的idx是j. 那么i - j其实就是代表不包含i这个元素的从j到i的长度, 也是我们之前讨论的以该元素打头且该元素是subarray中最小的, 那满足这样的subarray的个数就是这些subarray中最长的长度.

那么我们之前讨论的让该元素除了做打头的, 它还能做第1个, 第2个, 第3个… 停止的时候就是该元素的previous smaller的idx. 那其实就是现在的stack的top的值. 于是就有j - stack.peek(), 这表示被pop出的元素可以当第0个, 第1个, 第2个… 第j - stack.peek() - 1个(因为此时j前有j - stack.peek()个元素, 因此j此时在subarray的idx就是j - stack.peek() - 1).

至此就明白了为什么是array[currIdx] * (currIdx - stack.peek()) * (i - currIdx).

但这又有两个问题, 如果stack.pop完没东西了, 也就是某个元素在它的左侧没有比它小的数字了怎么办, 那就是j - 0 + 1就行了, 也就是j及以前所有的位置都可以作为开头. 但是如何很consistent的覆盖到这个情况呢? 那就是在原array前加一个Integer.MIN_VALUE. 这样, stack中永远有元素.

类似地, 如果遍历完数组, 发现stack中除了那个Integer.MIN_VALUE对应的idx之外还有其他idx呢? 这说明这些idx的右侧没有比它们小的. 那它们打头的subarray最长就是array.length - j. 我们的做法是在array屁股后面加一个Integer.MIN_VALUE. 强制把stack给pop空(当然除了stack最底部那个Integer.MIN_VALUE). 这样我们的写法就很consistent了.

时间复杂度: O(n) 每个元素最多进一次和出一次栈.
空间复杂度: O(n) 我们维护了一个栈.

额外注意的是第15行, 当时有一个case怎么都不过. 后来发现是15行的右侧计算可能会overflow. 于是我们需要手动让右侧变为long. 于是我加了一个1L. 这个1L必须加到前面, 因为表达式是从左往右计算的. 如果1L加到末尾, 那是overflow完了才变long, 此时就晚了.