leetcode 2104. 子数组范围和

超链接
思路二：单调栈
分析：我们以每个元素
去求当前元素为最大值的范围区间，也就是说 以当前元素为最大值，最左边能到达的最远和最右边能到达的最远形成的范围区间
去求当前元素为最小值的范围区间，也就是说 以当前元素为最小值，最左边能到达的最远和最右边能到达的最远形成的范围区间
举例，nums = {1,3,1,2,1}
当前元素是2，下标是3
那么最左边能达到nums[2]也就是中间那个1 下标是2
最右边能达到最后面，也就是最后那个1 下标是4
那么2对于答案的贡献度也就是2 * 2* 2=8，也就是以2为子数组的个数是4个，也就是24=8，这个4是这样来的，就是以2为最左元素，右边的子数组有两个，也即是{2],{2,1}，以2为最右元素有两个，也即是{1,2},{2}，一共就是22，4种方式。
也就是说，要包括总的个数是 ： (cur-left-1) * (right-cur-1)
那么这个问题也就成了让我们求，以每个元素为最大值左边范围和右边范围了
那么我们就可以使用单调栈来解决。
从栈底到栈顶，依次递减。
也就是说，当前元素比栈顶元素小，直接入栈。
当前元素比栈顶元素大，那么栈顶元素的最右就是当前元素所在的下标。栈顶的下一个元素就是栈顶元素的最右边。

以每个元素为最小值左边范围和右边范围是同理，就不解释了。看代码：
代码：

class Solution {
    int[][] dp = null;
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        return getMax(nums,n) - getMin(nums,n);
    }

    public long getMax(int[] nums, int n){
        int[] stack = new int[n];
        int top = - 1;
        long res  =0;
        for(int i = 0 ; i <= n;i++){
            while(top!=-1 && (i==n || nums[stack[top]] < nums[i])){
                int cur = stack[top--];
                int left = top == -1? -1 : stack[top];
                res = res + 1L *(cur-(left+1)+1) * (i-1-cur+1) * nums[cur]; //左边元素的个数 * 右边元素的个数 * 当前元素值   就等于当前元素在区间[left+1,i-1]  中必须包含当前元素的所有子数组个数   乘以当前元素
            }
            stack[++top] = i;
        }
        return res;
    }

    public long getMin(int[] nums, int n){
        int[] stack = new int[n];
        int top = - 1;
        long res  =0;
        for(int i = 0 ; i <= n;i++){
            while(top!=-1 && (i==n || nums[stack[top]] > nums[i])){
                int cur = stack[top--];
                int left = top == -1? -1 : stack[top];
                res = res + 1L*(cur-(left+1)+1) * (i-1-cur+1) * nums[cur]; //左边元素的个数 * 右边元素的个数 * 当前元素值   就等于当前元素在区间[left+1,i-1]  中必须包含当前元素的所有子数组个数 乘以当前元素
            }
            stack[++top] = i;
        }
        return res;
    }
}