2762. 不间断子数组 (opens new window)

1.TreeMap+滑动窗口

分析：滑动窗口内使用TreeMap维护子数组的最大值，最小值。

TreeMap具有如下性质：

• 插入元素时，在内部会对Key进行排序，默认是升序。
• 通过firstKey()和LastKey()两个API分别获取第一个key和最后一个key的值(最小key和最大key)
• cellingKey(K num)：返回大于等于num的最小key值；floorKey(K num)：返回小于等于num的最大key值
• pollFirstEntry()：删除key最小的元素。

在本题中，key存放nums数组元素，value存放每个元素出现的次数。通过首尾元素的key判断当前子数组是否不间断。每轮记录以left为左指针的最大子数组。

class Solution {
    public long continuousSubarrays(int[] nums) {
       long res=0;
        int left=0;
        TreeMap<Integer,Integer> treemap=new TreeMap<>();
        for(int i=0;i<nums.length;i++){
            treemap.put(nums[i],treemap.getOrDefault(nums[i],0)+1);
            while(treemap.lastKey()-treemap.firstKey()>2){
                res+=i-left;
                if(treemap.get(nums[left])==1) treemap.remove(nums[left]);
                else treemap.put(nums[left],treemap.get(nums[left])-1);
                left++;

            }
        }
        for(int i=left;i<nums.length;i++){
            res+=nums.length-i;
        }
        return res;
    }
}

2.优先级队列

事实上如果本题想不到使用TreeMap，那么需要设计实现一个数据结构A，并且满足

1. A中元素根据nums元素排好序，这样才能直接以O(1)的复杂度拿到子数组的上下界
2. 窗口移动时，因为需要移除边界元素，更新当前子数组的上下界，因此访问元素或者是直接删除操作复杂度需要为O(1)。

这里采用两个优先级队列PriorityQueue进行模拟，一个是递增队列，另一个是递减队列。具体如下：

• 分别从两个队列取出首元素，即为滑动窗口内的最大值和最小值
• remove(Object o)直接从队列删除对应元素。(事实上绝大多数数据结构如ArrayList，Deque，map，stack等都提供了这个方法，本质也是遍历一趟数据结构。然而个别数据结构遍历一趟代价比较大，比如先进先出之类的限制，因此虽然都是遍历，但是一般都直接调用对应API)

class Solution {
    public long continuousSubarrays(int[] nums) {
        long res=0;
        PriorityQueue<Integer> qmax=new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2){
                return o2-o1;
            }
        });
        PriorityQueue<Integer> qmin=new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2){
                return o1-o2;
            }
        });
        int left=0;
        for(int i=0;i<nums.length;i++){
            qmax.offer(nums[i]);
            qmin.offer(nums[i]);
            while(qmax.peek()-qmin.peek()>2){
                qmax.remove(nums[left]);
                qmin.remove(nums[left]);
                left++;
            }
            res+=i-left+1;
        }
        return res;
    }
}

耗时上很明显堆优先队列要比上一种TreeMap要慢很多，主要在remove操作上，堆删除元素后还需要shiftup和shiftdowm维护整个堆结构；而相比之下二叉红黑树的删除操作会快很多。

3.总结

对于需要维护子窗口、子数组的问题，设计数据结构时需要考虑以下几点：

• 子结构是否需要排序？排序又分几种：
  • 利用数据结构本身的比较器进行排序，比如PriorityQueue。不需要额外删除元素。
  • 基于自身增删操作来维护一个有序的数据结构，比如单调栈stack，单调队列Deque。这种方法往数据结构里添加新的元素后，一般都需要额外的移除操作。且数据结构大小都会小于子数组大小。
• 是否需要随机增删操作？删除元素时需要删除首尾元素还是指定元素。虽然一般都会提供remove(object)方法，但是时间复杂度相比于删除首尾元素会大很多。
• 数据结构内保存的元素是什么?就数组而言可能存在几种情况：
  • 保存索引下标。这种方式储存的信息量最大，获取元素对应值直接从nums根据索引访问。
  • 保存元素值。这种方式用的最多，一般用于“元素是否存在”相关的问题。
  • 保存元素出现的次数。