leetcode 2104. 子数组范围和

题目如下

数据范围

法一：
	观察到数组最长仅为1000那么我们可以使用复杂度为n方的方法搜索每一个子数组求出它们的的最大和最小值加到答案里面就行。
法二：
	法一的重复计算太多，许多包含同一个最小值或者最大值的子数组被重复计算了。事实上结果是由所有的最大值之和减去所有的最小值之和。在这里我们要先明白所有的最小值集合包含了数组的每一个数(即使是数组最大值x也是[x]这个子数组的最小值)也就是说我们令f(x)为以下标x的数对应的最小值数量，其中（0 <= x < n）然后我们再把所有的 num[x] * f(x)
相加就是所有最小值之和，所有最大值之和同理。然后我们相减即可得到答案。
至于具体的做法这里以找到以下标i为最小值的子数组数量为例：
	我们只需要找到l r其中l是左边第一个小于这个数的下标 r为右边第一个小于这个数的下标，那么我们可以从[l,i] [i,r]	得到数量。（排列组合）

通过代码
法一

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size();
        int min1,max1;
        for(int i = 0;i < n;i++){
            min1 = nums[i];
            max1 = min1;
            for(int j = i;j < n;j++){
                max1 = max(max1,nums[j]);
                min1 = min(min1,nums[j]);
                ans += ((long long)max1 - min1);
            }
           
        }
        return ans;
    }
};

法二

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size();
        stack<int> s1, s2;
        vector<int> l1(n), r1(n), l2(n), r2(n);
        long long min1 = 0, max1 = 0;
        for (int i = 0; i < n; i++) {
            while (!s1.empty() && nums[s1.top()] >= nums[i])
                s1.pop();
            l1[i] = (s1.empty()) ? -1 : s1.top();
            s1.push(i);
            while (!s2.empty() && nums[s2.top()] <= nums[i])
                s2.pop();
            r1[i] = (s2.empty()) ? -1 : s2.top();
            s2.push(i);
        }s1 = stack<int>();
        s2 = stack<int>();
        for (int i = n - 1; i >= 0; i--) {
            while (!s1.empty() && nums[s1.top()] > nums[i])
                s1.pop();
            l2[i] = (s1.empty()) ? n : s1.top();
            s1.push(i);
            while (!s2.empty() && nums[s2.top()] < nums[i])
                s2.pop();
            r2[i] = (s2.empty()) ? n : s2.top();
            s2.push(i);
        }
        for(int i = 0;i < n;i++){
            min1 += (long long)(i - l1[i]) * (l2[i] - i) * nums[i];
            max1 += (long long)(i - r1[i]) * (r2[i] - i) * nums[i];
            
        }
        return max1 - min1;
    }
};