2104. 子数组范围和

approach 1，遍历子数组

class Solution {
    public long subArrayRanges(int[] nums) {
        long res = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int max = nums[i];
            int min = nums[i];
            for (int j = i; j < n; j++) {
                max = Math.max(max, nums[j]);
                min = Math.min(min, nums[j]);
                res += max - min;
            }
        }
        return res;
    }
}

approach 2，单调栈+乘法组合运用

非正确单调栈用法：

class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        int[][] min = new int[n][2];
        int[][] max = new int[n][2];
        int l = 0, r = 1;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && nums[i] <= nums[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                min[i][l] = -1;
            } else {
                min[i][l] = stack.peek();
            }
            stack.push(i);
        }

        stack.clear();
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && nums[i] >= nums[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                max[i][l] = -1;
            } else {
                max[i][l] = stack.peek();
            }
            stack.push(i);
        }

        stack.clear();
        for (int i = n-1; i >= 0; i--) {
            while (!stack.empty() && nums[i] < nums[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                min[i][r] = n;
            } else {
                min[i][r] = stack.peek();
            }
            stack.push(i);
        }

        stack.clear();
        for (int i = n-1; i >= 0; i--) {
            while (!stack.empty() && nums[i] > nums[stack.peek()]) {
                stack.pop();
            }
            if (stack.empty()) {
                max[i][r] = n;
            } else {
                max[i][r] = stack.peek();
            }
            stack.push(i);
        }

        long minSum = 0, maxSum = 0;
        for (int i = 0; i < n; i++) {
            minSum += 1L * nums[i] * (i - min[i][l]) * (min[i][r] - i);
            maxSum += 1L * nums[i] * (i - max[i][l]) * (max[i][r] - i);
        }
        // System.out.println(Arrays.deepToString(min));
        // System.out.println(Arrays.deepToString(max));
        return maxSum - minSum;
    }
}

标准单调栈优化后：

class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        int[] s1 = new int[n];
        int[] s2 = new int[n];
        int t1 = -1, t2 = -1;

        long[] max = new long[n];
        long[] min = new long[n];

        for (int i = 0; i < n; i++) {
            while (t1 >= 0 && nums[i] >= nums[s1[t1]]) {
                int index = s1[t1--];
                int left = t1 >= 0 ? s1[t1] : -1;
                int right = i;
                max[index] = (long) (index - left) * (right - index);
            }
            s1[++t1] = i;

            while (t2 >= 0 && nums[i] <= nums[s2[t2]]) {
                int index = s2[t2--];
                int left = t2 >= 0 ? s2[t2] : -1;
                int right = i;
                min[index] = (long) (index - left) * (right - index);
            }
            s2[++t2] = i;
        }

        while (t1 >= 0) {
            int index = s1[t1--];
            int left = t1 >= 0 ? s1[t1] : -1;
            int right = n;
            max[index] = (long) (index - left) * (right - index);
        }

        while (t2 >= 0) {
            int index = s2[t2--];
            int left = t2 >= 0 ? s2[t2] : -1;
            int right = n;
            min[index] = (long) (index - left) * (right - index);
        }

        long maxSum = 0, maxMin = 0;
        for (int i = 0; i < n; i++) {
            maxSum += max[i] * nums[i];
            maxMin += min[i] * nums[i];
        }

        return maxSum - maxMin;
    }
}