907. Sum of Subarray Minimums

,

Sliding Window(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private static final int BASE = 1000000007;

    public int sumSubarrayMins(int[] arr) {
        int sum = 0;

        for (int windowLength = 1; windowLength <= arr.length; windowLength++) {
            Deque<Integer> decreaseDeque = new LinkedList<>(); // 从左至右非严格递减，含有重复的元素

            for (int j = 0; j < arr.length; j++) {
                int i = j - windowLength + 1; // window: [i, j]

                while (!decreaseDeque.isEmpty() && arr[j] < decreaseDeque.getFirst()) {
                    decreaseDeque.removeFirst();
                }
                decreaseDeque.offerFirst(arr[j]);

                int evictedIndex = i - 1;
                if (evictedIndex >= 0 && arr[evictedIndex] == decreaseDeque.getLast()) {
                    decreaseDeque.removeLast();
                }

                if (i >= 0) {
                    sum += decreaseDeque.getLast();
                    sum %= BASE;
                }
            }
        }

        return sum;
    }
}

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    private static final int BASE = 1000000007;

    private int safeGet(int[] arr, int index) {
        if (index == -1 || index == arr.length) {
            return 0;
        } else {
            return arr[index];
        }
    }

    public int sumSubarrayMins(int[] arr) {
        int sum = 0;

        Stack<Integer> increaseStack = new Stack<>(); // 从底至顶递增，栈中存储的为元素索引，包含重复元素

        // 遍历时两端增加哨兵
        for (int i = -1; i <= arr.length; i++) {
            while (!increaseStack.isEmpty() && safeGet(arr, i) < safeGet(arr, increaseStack.peek())) { // 注意栈中存储的为索引，注意此处为小于，且不能使用等于，如果使用等于，那么两侧的哨兵会导致最后一个哨兵计算时 increaseStack.peek() 触发 EmptyStackException
                // 遇到了高度更低的柱子
                int midIndex = increaseStack.pop();
                int leftIndex = increaseStack.peek();
                int rightIndex = i;

                int m = midIndex - leftIndex - 1; // arr[midIndex] 左侧大于 arr[midIndex] 的元素个数
                int n = rightIndex - midIndex - 1; // arr[midIndex] 右侧大于等于 arr[midIndex] 的元素个数
                int count = 1 + m + n + m * n;
                sum += (long) arr[midIndex] * count % BASE; // 注意此处取值应该为 arr[midIndex]
                sum %= BASE;
            }

            increaseStack.push(i);
        }

        return sum;
    }
}

对于重复元素，以上解法保证了只统计一次，具体可以使用 [3, 1, 1] 在草稿纸上模拟以加深理解。

References

907. Sum of Subarray Minimums