题目分析

本题是第315长周赛的最后一题，其实难度并不大，这种范围性的题目，小伙伴们一定要想到滑动窗口/双指针的做法。

滑动窗口/双指针

滑动窗口/双指针是我们的老朋友了，我们可以枚举左端点，然后让右端点努力向后走，直到不符合条件。

这个题目我们可以发现，如果某个值不再minK和maxK之间，假设索引为k，那么子数组一定不能包含索引k，即子数组的最大右端点为k - 1，或者最小左端点为k + 1。

所以根据不符合条件的点，可以将数组分成很多个段。只要考虑每一段中有多少符合条件的子数组即可。

我们以某一段为例，假设left为起点，因为right会一直向后走，所以right - 1为该段右端点。设第一次出现minK的位置为minIdx，第一次出现maxK的位置为maxIdx，那么从left到Max(minIdx, maxIdx)的区间是符合条件的。从left到right - 1的区间也是符合条件的。因此以left为起点的区间，符合长度的数组数量为right - 1 - Max(minIdx, maxIdx) + 1 = right - Max(minIdx, maxIdx)。

然后遍历left即可，注意在left移动的时候，可能会动态修改第一次出现minK和maxK的位置，这时可以维护一个队列，每次从如果nums[right] = minK或者maxK，则从队尾插入下标，如果nums[left] = minK或者maxK，则从队头删除下标

要注意本题的一个细节，left和right可能会相等。因此不能写if…else…，只可以写两个if

所以算法的**时间复杂度为O(n)，空间复杂度为O(n)**。

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long res = 0;
        int n = nums.length;
        LinkedList<Integer> minQ = new LinkedList<>();
        LinkedList<Integer> maxQ = new LinkedList<>();
        for (int left = 0, right = 0; left < n; left++) {
            right = Math.max(right, left);
            while (right < n && nums[right] >= minK && nums[right] <= maxK) {
                if (nums[right] == minK) {
                    minQ.addLast(right);
                }
                if (nums[right] == maxK) {
                    maxQ.addLast(right);
                }
                right++;
            }
            if (!minQ.isEmpty() && !maxQ.isEmpty()) {
                res += right - Math.max(minQ.getFirst(), maxQ.getFirst());
            }
            if (nums[left] == minK) {
                minQ.removeFirst();
            }
            if (nums[left] == maxK) {
                maxQ.removeFirst();
            }
        }
        return res;
    }
}

优化滑动窗口/双指针

我刚刚看这个题目的时候，只想到了第一种解法，其实还有优化空间复杂度的解法。

上面的做法是左端点每次移动一个位置，搜索右端点不符合条件的第一次出现的位置。那么转变一下思维，让右端点每次移动一个位置，搜索左端点不符合条件的最后一次出现的位置。

对于右端点为right的情况，因为左端点是不符合条件的最后一次出现的位置。假如最后一次出现minK的位置为minIdx，最后一次出现maxK的位置为maxIdx，那么从left + 1到right都是符合条件的。从Min(minIdx, maxIdx)到right也都是符合条件的。所以符合条件的子数组个数为Min(minIdx, maxIdx) - (left + 1) + 1 = Min(minIdx, maxIdx) - left。

因此此时保存的都是最后一次出现的位置，因此在移动右端点的时候，可以动态更新minIdx，maxIdx和left，所以不需要队列保存索引。

这里要注意，因为left是不符合条件的最后一次出现的位置，如果某个值不符合条件，那么left会及时更新，就会导致Min(minIdx, maxIdx) < left，因此要取Max(Min(minIdx, maxIdx) < left, 0)。

所以算法的**时间复杂度为O(n)，空间复杂度为O(1)**。

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long res = 0;
        int n = nums.length;
        int minIdx = -1;
        int maxIdx = -1;
        int left = -1;
        for (int right = 0; right < n; right++) {
            if (nums[right] > maxK || nums[right] < minK) {
                left = right;
                continue;
            }
            if (nums[right] == minK) {
                minIdx = right;
            }
            if (nums[right] == maxK) {
                maxIdx = right;
            }
            res += Math.max(Math.min(minIdx, maxIdx) - left, 0);
        }
        return res;
    }
}

刷题总结

本题的难度适中，是小伙伴们必须要学会的滑动窗口/双指针问题。