题目

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/

题解

一看数据规模，这题只能 O(1)

乍一看，以为是单调栈。一画图，发现是一个排列组合问题。思路如下：

首先，将大于 right 的数字圈出来，看作是挡板，把整个数组分割成好几个段。
每个段中，包含小于 left 的数字，这些数字是不能单独成群的。
所以每个段中的所有可能组合数量 = 段内所有可能组合数量 - 不能单独成群的数字的组合数量。
计算组合数量的时候，用等差求和公式 1+2+3+...+n = (首项+末项)*项数/2

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        long result = 0;
        
        long valid = 0; // 连续的小于等于right个数
        long below = 0; // 连续的小于left个数

        if (nums[0] <= right) valid++;
        if (nums[0] < left) below++;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > right) { // above
                if (valid > below) {
                    result += (1 + valid) * valid / 2;
                    result -= (1 + below) * below / 2;
                }
                valid = 0;
                below = 0;
            } else if (nums[i] < left) { // below
                valid++;
                below++;
            } else { // middle
                valid++;
                if (nums[i - 1] < left) {
                    result -= (1 + below) * below / 2;
                }
                below = 0;
            }
        }
        // 清算末尾
        result -= (1 + below) * below / 2;
        result += (1 + valid) * valid / 2;
        return (int) result;
    }
}