# 2104. Sum of Subarray Ranges
###### tags: `Leetcode` `Medium` `Stack` `Monotonic Stack`
Link: https://leetcode.com/problems/sum-of-subarray-ranges/description/
## 思路
算出每个数字做smallest的次数和做largest的次数 就能求出答案
那么如何知道一个数字做smallest/largest的次数呢
答案就是用单调栈
当我们加一个新元素nums[i]
导致原本栈顶的一个元素在min stack/max stack被pop出来的时候 我们就会知道在(pop完栈顶元素新的栈顶,i)这个区间内 被pop出来的元素是最小/最大值
因此以它为最小/最大值的subarray数就自然而然能求出来了
## Code

class Solution {
    public long subArrayRanges(int[] nums) {
        long ans = 0;
        Stack<Integer> min = new Stack<>();
        Stack<Integer> max = new Stack<>();
        for(int i=0; i<=nums.length; i++){
            while(!min.isEmpty() && (i==nums.length || nums[min.peek()]>nums[i])){
                int cur = min.pop();
                ans -= (long)nums[cur]*(i-cur)*(cur-(min.isEmpty()?-1:min.peek()));
            }
            min.add(i);
            while(!max.isEmpty() && (i==nums.length || nums[max.peek()]<nums[i])){
                int cur = max.pop();
                ans += (long)nums[cur]*(i-cur)*(cur-(max.isEmpty()?-1:max.peek()));
            }
            max.add(i);
        }
        return ans;
    }
}