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
| class Solution {
public long subArrayRanges(int[] nums) {
List<Integer> list = new ArrayList<>();
list.add(Integer.MIN_VALUE);
for (int num : nums) {
list.add(num);
}
list.add(Integer.MIN_VALUE);
Deque<Integer> stack = new ArrayDeque<>();
long ans = 0;
for (int i = 0; i < list.size(); i++) {
while (!stack.isEmpty() && list.get(i) < list.get(stack.peek())) {
int currIdx = stack.pop();
ans -= 1L * list.get(currIdx) * (currIdx - stack.peek()) * (i - currIdx);
}
stack.push(i);
}
stack.clear();
list.set(0, Integer.MAX_VALUE);
list.set(list.size() - 1, Integer.MAX_VALUE);
for (int i = 0; i < list.size(); i++) {
while (!stack.isEmpty() && list.get(i) > list.get(stack.peek())) {
int currIdx = stack.pop();
ans += 1L * list.get(currIdx) * (currIdx - stack.peek()) * (i - currIdx);
}
stack.push(i);
}
return ans;
}
}
|
和907是一个类型. 先让能做minimum的数字做的次数 * 它的值减到ans中; 在让能做maximum的数字做的次数 * 它的值加到ans中, 最后就是答案. 我只能说牛逼.
时间复杂度: O(n)
空间复杂度: O(n)
