[Java] solution with explanation beating 100% - O(N)
We will go through the nums once from left to right and count the valid subarrays ending at the current index. Summing up all the results will give us the final
We will go through the `nums` once from left to right and count `the valid subarrays ending at the current index`. Summing up all the results will give us the final result.\n\nFor each num, we can categorize them into three types:\n1. nums in between of [left, right]. We could construct valid subarrays ending with the current num all the way till the last index that\'s larger than `right`. For example, left = 2, right = 5, nums = [6,5,4,`3`,2,1,0]. At position 4, we have num as `3`, we can construct subarrays ending with `3` till position 0(exclusive), which is the index with the last num larger than the right: [3], [4,3], [5,4,3]. Based on this, we know that we need to note the latest index of the num that\'s larger than the right;\n2. nums less than left. This num itself cannot construct the valid subarray; but if we have some other nums in between of [left, right] before that, we can still construct valid subarrys ending with the current num together with those nums in between of [left, right]. However, we cannot go too far; we can only construct valid subarrys till the num that\'s larger than the right. For example, left = 2, right = 5, nums = [6,5,4,3,2,1,`0`]. At position 6, we have num as `0`, which is smaller than the left, but we can construct subarrays with previous nums till `6`. [1,0] is still not valid because both of them are smaller than the left, so this tell us that we need to start with the num that\'s in between of [left, right], which is `2` in this case, and till the num that\'s larger than right, which is `6`. Based on this, we realize that we need a running counter to tell us the distance between the last number in between of [left, right] and the last number larger than right. This running count will be updated whenever we hit the num in case 1 and case 3.\n3. nums larger than right. There will be no valid subarrays ending with this number and when we hit this number, it will reset our running counter to 0 and we will also update the index of the last number larger than right to the current index.\n\nThe final code looks like below:\n```\nclass Solution {\n    public int numSubarrayBoundedMax(int[] nums, int left, int right) {\n        int result = 0;\n        \n        int lastTooLarge = -1; // the index of last num that\'s larger than the right; we initialize it as -1\n        int count = 0;\n        int index = 0;\n        while (index < nums.length) {\n            if (nums[index] <= right && nums[index] >= left) {\n                count = index - lastTooLarge; // update the running counter: distance between the last valid number to the last num larger than the right\n                result += count; // construct with nums between [last number larger than the right, last valid number in between of left and right]\n            } else if (nums[index] < left) {\n                result += count; // construct with nums between [last number larger than the right, last valid number in between of left and right]\n            } else {\n                lastTooLarge = index; // update the index of the last num that\'s larger than the right\n                count = 0; // reseet the running counter to 0\n            }\n            index++;\n        }\n        \n        return result;\n    }\n}\n```
['Java']