image.png

    题目分析：假设有m个子数组，原问题等价于 m个子数组最大值与最小值之差的累加。怎么求不同子数组的最大值和最小值呢？详见leetcode 907。

    1. class Solution {
    2.     public long subArrayRanges(int[] nums) {
    3.         int n = nums.length;
    5.         long[] min_left = new long[n];
    6.         long[] min_right = new long[n];
    7.         long[] max_left = new long[n];
    8.         long[] max_right = new long[n];
    10.         Deque<Integer> min_stack = new LinkedList<>();
    11.         Deque<Integer> max_stack = new LinkedList<>();
    14.         //1.计算min_left
    15.         //从左到右，依次计算nums[i]左侧的第一个不小于nums[i]的数的下标
    16.         for(int i = 0; i < n; i++){
    17.             while(!min_stack.isEmpty() && nums[min_stack.peek()] >= nums[i]){
    18.                 min_stack.pop();
    19.             }
    20.             if(min_stack.isEmpty()){
    21.                 min_left[i] = -1;
    22.             }else{
    23.                 min_left[i] = min_stack.peek();
    24.             }
    26.             min_stack.push(i);
    27.         }
    29.         //2.计算min_right
    30.         //从右到左，依次计算nums[i]右侧的第一个大于nums[i]的数的下标
    31.         min_stack.clear();
    32.         for(int i = n -1; i >= 0; i--){
    33.             while(!min_stack.isEmpty() && nums[min_stack.peek()] > nums[i]){
    34.                 min_stack.pop();
    35.             }
    36.             if(min_stack.isEmpty()){
    37.                 min_right[i] = n;
    38.             }else{
    39.                 min_right[i] = min_stack.peek();
    40.             }
    41.             min_stack.push(i);
    42.         }
    44.         //3.计算max_left
    45.         //从左到右，依次计算nums[i]左侧第一个大于等于nums[i]的数的下标
    46.         for(int i = 0; i < n; i++){
    47.             while(!max_stack.isEmpty() && nums[max_stack.peek()] <= nums[i]){
    48.                 max_stack.pop();
    49.             }
    50.             if(max_stack.isEmpty()){
    51.                 max_left[i] = -1;
    52.             }else{
    53.                 max_left[i] = max_stack.peek();
    54.             }
    55.             max_stack.push(i);
    56.         }
    58.         //4.计算max_right
    59.         //从右到左，依次计算nums[i]右侧第一个大于nums[i]的数的下标
    60.         max_stack.clear();
    61.         for(int i = n -1; i >= 0; i--){
    62.             while(!max_stack.isEmpty() && nums[max_stack.peek()] < nums[i]){
    63.                 max_stack.pop();
    64.             }
    65.             if(max_stack.isEmpty()){
    66.                 max_right[i] = n;
    67.             }else{
    68.                 max_right[i] = max_stack.peek();
    69.             }
    70.             max_stack.push(i);
    71.         }
    73.         long ans = 0;
    74.         for(int i = 0; i < n; i++){
    75.             ans += (i - max_left[i]) * (max_right[i] - i) * nums[i];
    76.             ans -= (i - min_left[i]) * (min_right[i] - i) * nums[i];
    77.             //ans += ((i - max_left[i]) * (max_right[i] - i) - (i - min_left[i]) * (min_right[i] - i)) * nums[i];
    78.         }
    79.         return ans;
    80.     }
    81. }