算法模板--区间类型

1.区间合并

public int[][] merge(int[][] intervals) {
    // L指向区间开头，R指向区间尾
    // 有覆盖的就更新ed
    // 没有覆盖的就放入ans, 并更新st和ed
    List<int[]> ans = new ArrayList<>();
    // 先按区间头排序
    Arrays.sort(intervals, Comparator.comparingInt(arr -> arr[0]));
    for (int[] interval : intervals){
        int L = interval[0], R = interval[1];
        if (ans.size() == 0 || ans.getLast()[1] < L){
            // 发现新区间
            ans.add(new int[]{L, R});
        }else{
            // 发现重叠区间
            ans.getLast()[1] = Math.max(ans.getLast()[1], R);
        }
    }
    return ans.toArray(new int[ans.size()][2]);
}

2.单调栈

应用：为数组中每个数找出它左边距离最近的比它小（大）的数

思想：当a(x)<=a(y)，且y>x时，删掉a(x)

操作：把大于a(i)的数全部出栈后，a(i)再入栈

for (int i = 0; i < n; i++){
    // 栈不空并且栈顶元素大于输入元素
    while (!stack.isEmpty() && stack.peek() > nums[i])
        stack.pop();
    stack.push(nums[i]);
}

3.单调队列（双端队列）

应用：找出滑动窗口中的最值（滑动窗口头部坐标：i-k+1, k是窗口长度）

操作：队列中存窗口元素的下标，如果a(i)比队尾下标对应的元素小，则队尾下标出队，再入a(i)下标

Deque<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++){
    // 队不空并且队头已经滑出了窗口
    while (!q.isEmpty() && i - k + 1 > q.getFirst())
        q.removeFirst();
    // 把队尾下标出队
    while (!q.isEmpty() && check(q.getLast(), i))
        q.removeLast();
    // 坐标入队
    q.addLast(i);
    // 对头元素就是最值
    if (i - k + 1 >= 0)
        print(q.getFirst());
}

4.长度为k的滑动窗口维护窗口中的元素之和

for (int i = 0; i < n; i++){ // 遍历窗口尾部
    int head = i - k + 1; // 窗口头部
    // 窗口头部没滑到数组头部
    if (head < 0)｛
        sum += nums[i];
        continue;
    ｝
    // 划入
    sum += nums[i];
    // 操作
    ...
    // 划出
    sum -= nums[head];
}

更一般的，

// 窗口从数组的start开始, 每次滑动m
for (int i = start; i < n; i += m){ // 遍历窗口尾部
    int head = i - k + 1; // 窗口头部
    // 窗口头部没滑到数组头部
    if (head < start)｛
        ...
        continue;
    ｝
    // 划入
    ...
    // 操作
    ...
    // 划出
    ...
}

5.不定长的滑动窗口

遍历右端点，左端点找满足条件的

for (int r = 0; r < n; r++){
    sum += nums[r];
    while (sum > target){
        sum -= nums[l];
        l++;
    }
}