LeetCode——子数组范围和 C++

题目描述：

本题为了实现O(n)的时间复杂度采用了单调栈的解法。

通俗来说就是找出每一个元素向左看与向右看的相比较于这个元素的更大值和更小值（这意味着需要四个数组来存储位置下标）来确定该元素在左右两个方向的那些子数组中充当最大和最小值，具体实现四个数组的方法为用大值栈和小值栈来存储遍历的元素。当不满足条件时将数据弹出，完成当前回合遍历时将数据压入栈。

最后用公式来求解出最小值之和以及同理的最大值之和，最大和与最小和相减即为答案。

PS：当出现相等元素的时候，可以定义i的左右优先级来判断大小，即i+1对应位置元素大于i位置元素，i-1位置元素小于i位置元素。用这个定义可以完成程序设计。

完整代码如下：

long long subArrayRanges(vector<int>& nums) {
        stack<long long>min,max;
        vector<long long >min_l(nums.size()),min_r(nums.size()),max_l(nums.size()),max_r(nums.size());
        long long min_num=0,max_num=0;
        for(int i=0;i<nums.size();i++){
            while(!min.empty()&&nums[min.top()]>nums[i])min.pop();
            min_l[i]=min.empty()?-1:min.top();
            min.push(i);
            while(!max.empty()&&nums[max.top()]<=nums[i])max.pop();
            max_l[i]=max.empty()?-1:max.top();
            max.push(i);
        }
        min=stack<long long>();
        max=stack<long long>();
        for(int i=nums.size()-1;i>=0;i--){
            while(!min.empty()&&nums[min.top()]>=nums[i])min.pop();
            min_r[i]=min.empty()?nums.size():min.top();
            min.push(i);
            while(!max.empty()&&nums[max.top()]<nums[i])max.pop();
            max_r[i]=max.empty()?nums.size():max.top();
            max.push(i);
        }
        for(int i=0;i<nums.size();i++){
            min_num+=(i-min_l[i])*(min_r[i]-i)*nums[i];
            max_num+=(i-max_l[i])*(max_r[i]-i)*nums[i];
        }
        return max_num-min_num;
    }