2104. Sum of Subarray Ranges

gistfile1.txt

class Solution {
    public long subArrayRanges(int[] nums) {
        //Monotonic Stack O(n)
        int n = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] leftMin = new int[n];
        int[] rightMin = new int[n];
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        for(int i = 0; i < n; i++) {
            leftMin[i] = i + 1;
            leftMax[i] = i + 1;
            rightMin[i] = n - i;
            rightMax[i] = n - i;
        }

        //PLE
        //[1,4,2,3]
        //[-1,1,1,2]
        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                stack.pop();
            }
            
            if(!stack.isEmpty()) {
                leftMin[i] = i - stack.peek();
            }
            
            stack.push(i);
        }
        
        //NLE
        //[1,4,2,3]
        //[-1,2,-1,-1]
        stack.clear();
        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                int prevIndex = stack.pop();
                rightMin[prevIndex] = i - prevIndex;
            }
            
            stack.push(i);
        }
        
        //PGE
        //[1,4,2,3]
        //[-1,-1,4,4]
        stack.clear();
        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                stack.pop();
            }
            
            if(!stack.isEmpty()) {
                leftMax[i] = i - stack.peek();
            }
            
            stack.push(i);
        }
        
        //NGE
        //[1,4,2,3]
        //[4,-1,3,-1]
        stack.clear();
        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int prevIndex = stack.pop();
                rightMax[prevIndex] = i - prevIndex;
            }
            
            stack.push(i);
        }
        
        long result = 0;
        for(int i = 0; i < n; i++) {
            result += nums[i] * ((long)leftMax[i] * rightMax[i] - leftMin[i] * rightMin[i]);
        }
        
        return result;
    }
}