[数据结构与算法]力扣 2444. 统计定界子数组的数目

题目来源：https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/

大致题意：
给一个数组和两个数，这两个数分别表示子数组的最大值与最小值

求给定数组中最值为给定值的子数组的个数

思路

首先考虑，假设在数组中给定最值的索引为 x 和 y，那么如何确定以 x 和 y 处元素为最值的子数组个数？

1. 确定左右侧不以 x 和 y 出元素为最值的边界为 l 和 r
2. 那么以 x 和 y 处元素为最值的子数组个数为 (min(x, y) - l) * (max(i, j) - r)

题目规定了数组长度为 10⁵，如果每次枚举到两个最值，再向两侧枚举边界的时间复杂度会达到 O(n²)

其实不需要每次都枚举边界，因为子数组连续的特性，后一个出现的以 x 和 y 处元素为最值的子数组左边界一定大于前一个的左边界，不需要进行重复的判断

具体解题时，在遍历过程中可以通过三个标志位：

• border 表示最近出现的大于给定最大值或者小于给定最小值的元素的索引，其对应满足条件的子数组左边界
• min 表示最近出现的最小值的索引
• max 表示最近出现的最大值的索引

那么在遍历时，如果已经确定左边界，可以在更新右边界的过程中统计以 x 和 y 处元素为最值的子数组个数，具体方法为

• min(min, max) - border
• 即在确定子数组的左边界后，在更新右边界的同时，更新对应左边界子数组的个数
• 上述计算可能出现负值，即以当前数结尾的子数组不以 x 和 y 处元素为最值，此时不更新子数组个数即可

具体看代码：

	public long countSubarrays(int[] nums, int minK, int maxK) {
        int n = nums.length;
        long ans = 0;
        // 初始化三个标志位
        int min = -1;
        int max = -1;
        int border = -1;
        for (int i = 0; i < n; i++) {
        	// 更新标志位
            if (nums[i] < minK || nums[i] > maxK) {
                border = i;
            }
            if (nums[i] == minK) {
                min = i;
            }
            if (nums[i] == maxK) {
                max = i;
            }
            // 更新满足条件子数组的个数
            // 这里使用max（0， 以当前数结尾的满足条件子数组个数）来避免负数问题
            ans += Math.max(0, Math.min(min, max) - border);
        }
        return ans;
    }