907. Sum of Subarray Minimums 发表于 2022-08-25 Sliding Window(TLE)1234567891011121314151617181920212223242526272829303132class 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; }} Stack12345678910111213141516171819202122232425262728293031323334353637class 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] 在草稿纸上模拟以加深理解。 Reference907. Sum of Subarray Minimums