LC.P2104[子数组范围和]

方法一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public long subArrayRanges(int[] nums) {
        long ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for (int j = i; j < n; ++j) {
                min = Math.min(min, nums[j]);
                max = Math.max(max, nums[j]);
                ans += max - min;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

方法二：单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<>();
        long max = 0;
        for (int i = 0; i <= n; ++i) {
            while (!stack.isEmpty() && (i == n || nums[stack.peek()] < nums[i])) {
                int j = stack.pop();
                max += (long) nums[j] * (i - j) * (j - (stack.isEmpty() ? -1 : stack.peek()));
            }
            stack.push(i);
        }
        stack.clear();
        long min = 0;
        for (int i = 0; i <= n; ++i) {
            while (!stack.isEmpty() && (i == n || nums[stack.peek()] > nums[i])) {
                int j = stack.pop();
                min += (long) nums[j] * (i - j) * (j - (stack.isEmpty() ? -1 : stack.peek()));
            }
            stack.push(i);
        }
        return max - min;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$