LeetCode 85双周赛（补记）

2379. 得到K个黑块的最少涂色次数

题目描述

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 ‘W’ 要么是 ‘B’ ，表示第 i 块的颜色。字符 ‘W’ 和 ‘B’ 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

示例

输入：blocks = “WBBWWBBWBW”, k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = “BBBBBBBWBW” 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

思路

只需要用一个长度为k的窗口，从左到右滑过整个字符串，每次统计窗口内白色块数目，求个最小值即可。

class Solution {
    public int minimumRecolors(String blocks, int k) {
        int n = blocks.length();
        int ans = n, cnt = 0;
        for (int i = 0, j = 0; i < n; i++) {
            char c = blocks.charAt(i);
            if (c == 'W') cnt++;
            if (i - j + 1 == k) {
                ans = Math.min(ans, cnt);
                if (blocks.charAt(j) == 'W') cnt--;
                j++;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2380. 二进制字符串重新安排顺序需要的时间

题目描述

给你一个二进制字符串 s 。在一秒之中，所有 子字符串 “01” 同时 被替换成 “10” 。这个过程持续进行到没有 “01” 存在。

请你返回完成这个过程所需要的秒数。

示例

输入：s = “0110101”
输出：4
解释：
一秒后，s 变成 “1011010” 。
再过 1 秒后，s 变成 “1101100” 。
第三秒过后，s 变成 “1110100” 。
第四秒后，s 变成 “1111000” 。
此时没有 “01” 存在，整个过程花费 4 秒。
所以我们返回 4 。

1 < s.length <= 1000

思路

由于这道题的数据范围比较小，可以直接用暴力来进行模拟，周赛时我也是直接用暴力做的。

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        char[] cs = s.toCharArray();
        int ans = 0, n = cs.length;
        while(true) {
            boolean end = true;
            for (int i = 0; i < n; i++) {
                if (i + 1 < n && cs[i] == '0' && cs[i + 1] == '1') {
                    end = false;
                    swap(cs, i, i + 1);
                    i++;
                }
            }
            if (end) break;
            else ans++; //本轮有发生交换, 秒数加1
        }
        return ans;
    }

    private void swap(char[] cs, int i, int j) {
        char t = cs[i];
        cs[i] = cs[j];
        cs[j] = t;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

进阶

你能以$O(n)$的时间复杂度解决该题吗？

观察发现，每次操作，都相当于做了一次交换，都会将01变成10，而交换之后，0放到右边了，这个0要么在下一轮中和后面的1组成新的01以继续进行交换，要么其后面是0。所以，我们操作过程中，始终会把1往前放，把0往后放。最终一定会得到形如11110000这样，前半部分全为1，后半部分全为0的状态。但是0和1的个数分别都没有变化，

我们可以回过头来看看，为什么暴力不会超时，因为实际相当于把0不断往右移动，那么最坏的情况下，0全部都在左边，此时的操作轮数为n - 1，所以最坏情况下，操作n - 1轮，每轮需要遍历一次字符串，时间复杂度$O(n^2)$。

我们可以这样来考虑，每次交换，会使得一个0，往后移动一位。而最终全部0都会紧凑的排在右边。

那么我们从最右侧往左走，遇到的第一个0，其最终一定会位于右侧的第一个位置；遇到的第二个0，最终会位于右侧的第二个位置。则我们对每个0，计算一下将其从最初位置，交换到最终位置，一共需要多少次交换，然后做一下累加？看这个思路行不行。

我们用上面样例数据来测试一下

输入：s = “0110101”
输出：4
解释：
一秒后，s 变成 “1011010” 。
再过 1 秒后，s 变成 “1101100” 。
第三秒过后，s 变成 “1110100” 。
第四秒后，s 变成 “1111000” 。

右侧的第一个0，只需要一次交换就到了最终位置，可以看到第一轮过后，右侧第一个0就到达了最终位置；

右侧第二个0，最终位置是右侧第二个位置，其初始位置距最终位置相差2，其也是需要2轮才到达最终位置；

右侧第三个0，最终位置是右侧第三个位置，其初始位置距最终位置相差4，其也是在第4轮后才到达最终位置；

诶。这样来看，只需要求解，从左侧开始数的第一个0，其到达最终位置需要花费的轮数即可，只有最左侧的0到达最终位置，整个操作过程才会停止。

但是注意，对于某个位置的0，不是每一轮都会发生移动的，我们换一个样例：10001，其操作过程如下

初始状态 10001

第1轮操作后 10010

第2轮操作后 10100

第3轮操作后 11000

对于左侧第一个0，在第三轮时才发生了移动。即连续的0无法在同一轮中向右移动。会被堵住。

--------自己的思路卡在这里就走不下去了。

于是直接打开题解。（菜鸡的苦笑.jpg）

换一下思路，0向右移动，等同于1向左移动。我们考虑1向左移动。

用动态规划，我们定义f[i]表示[0,i]区间内，把全部的1移动到左边，需要的秒数。

接下来分类讨论，还是根据最后一位的情况来分类

• 若s[i] = 0，则这一位无需移动，需要的秒数等同于[0,i - 1]需要的秒数，即f[i] = f[i - 1]

• 若s[i] = 1，在这一位可能需要移动。

  • 若在[0,i - 1]区间内不存在0，则说明此时已经全部是1了，无需移动，此时f[i] = 0

  • 若[0,i - 1]区间内存在0，设0的个数为cnt0，而每一次和0交换，只能将该位置的1往左挪动一位，则至少需要的秒数为cnt0（若该1左侧全为0，则需要cnt0秒）；故第一个下界是cnt0；而当往左移动该位置的1时，如果途中遇到左侧恰好也是1，形成11这样的状态时，还需要等左侧的1挪走后，该1才能继续往左走。（11这种情况可以理解为堵车，右侧的1被左侧的1堵住了，此时两个1不能同时往左挪动）。只有当两个1没有相邻时，它们可以同时往左挪动，但两个1之间距离不会超过一（因为只要形成101，只要拉开一个位置的距离，则右侧的1下一轮一定会往左挪动跟上去；而左侧的1往左移动拉开距离时，一定会把0交换过来，所以也不会形成111这样的情况）。所以该1的挪动次数，最多是其左侧遇到的第一个1的挪动次数+1（至少要等一秒，等左侧相邻的1挪走）（该1往左移动，可能会在途中被左侧一个相邻的1给挡住）。所以此时f[i] = max(cnt0, f[i - 1] + 1)。

    注意，这里用f[i - 1]从定义上讲是[0,i - 1]需要的秒数，而不是左侧第一个1需要的秒数，但是可以用它来表示该1左侧的第一个1需要额秒数；当i - 1这个位置是1，则显然成立；若i - 1的位置是0，f[i - 1] = f[i - 2]，这个相等关系会一直传递过去，直到遇到左侧第一个1，所以可以f[i - 1]其实和当前1左侧的第一个1的f值是相等的

边界条件：f[0] = 0，当只考虑第一位时，无需做任何操作，需要秒数为0。

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        int[] f = new int[n];
        f[0] = 0;
        int cnt0 = cs[0] == '0' ? 1 : 0;
        for (int i = 1; i < n; i++) {
            if (cs[i] == '0') {
                f[i] = f[i - 1];
                cnt0++;
            } else if (cnt0 > 0) {
                f[i] = Math.max(cnt0, f[i - 1] + 1);
            }
        }
        return f[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以利用滚动数组的思想，将空间复杂度优化为常数级别：

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        int f = 0, cnt0 = 0;
        for (int i = 0; i < n; i++) {
            if (cs[i] == '0') cnt0++;
            else if (cnt0 > 0) f = Math.max(f + 1, cnt0);
        }
        return f;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2381. 字母移位II

题目描述

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。

将一个字符 向后 移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 ‘z’ 变成 ‘a’）。类似的，将一个字符 向前 移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 ‘a’ 变成 ‘z’ ）。

请你返回对 s 进行所有移位操作以后得到的最终字符串。

思路

经典差分。每一轮，都需要对一个区间内的所有数，都加上一个常数，这道题比较特殊，只会+1（向后移位）或者-1（向前移位），注意这道题是循环的，需要对26取模。经过若干轮后，求最终数组。

class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        int n = s.length();
        int[] num = new int[n + 1]; //差分数组
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            add(num, i, i, u); // 构造差分数组
        }
        for (int[] sh : shifts) {
            add(num, sh[0], sh[1], sh[2] == 0 ? -1 : 1);
        }
        // 差分数组还原
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) num[i] = (num[i] + num[i - 1]) % 26;
            sb.append((char) (num[i] + 'a'));
        }
        return sb.toString();
    }

    // 对区间[i,j]上的数都加上一个常数c
    private void add(int[] num, int i, int j, int c) {
        // 差分标准写法
        //num[i] += c;
        //num[j + 1] -= c;
        // 需要取模
        num[i] = (num[i] + c + 26) % 26; // 注意这里也要+26, 因为c可能是负数
        num[j + 1] = (num[j + 1] - c + 26) % 26;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2382. 删除操作后的最大子段和

题目描述

给你两个下标从 0 开始的整数数组 nums 和 removeQueries ，两者长度都为 n 。对于第 i 个查询，nums 中位于下标 removeQueries[i] 处的元素被删除，将 nums 分割成更小的子段。

一个 子段 是 nums 中连续 正 整数形成的序列。子段和 是子段中所有元素的和。

请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]是第 i 次删除操作以后的 最大 子段和。

注意：一个下标至多只会被删除一次。

示例

输入：nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
输出：[14,7,2,2,0]
解释：用 0 表示被删除的元素，答案如下所示：
查询 1 ：删除第 0 个元素，nums 变成 [0,2,5,6,1] ，最大子段和为子段 [2,5,6,1] 的和 14 。
查询 2 ：删除第 3 个元素，nums 变成 [0,2,5,0,1] ，最大子段和为子段 [2,5] 的和 7 。
查询 3 ：删除第 2 个元素，nums 变成 [0,2,0,0,1] ，最大子段和为子段 [2] 的和 2 。
查询 4 ：删除第 4 个元素，nums 变成 [0,2,0,0,0] ，最大子段和为子段 [2] 的和 2 。
查询 5 ：删除第 1 个元素，nums 变成 [0,0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。
所以，我们返回 [14,7,2,2,0] 。

思路

由于需要求解一段区间内的连续和，容易想到前缀和；其次，每次会选择一个点，从这个点切开。随着每次选择一个点切开，会从一个区间，逐渐被切成很多给区间，并最终全部被切掉。图示如下

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-u1vcr7WP-1662089451493)(C:\Users\yogurt\AppData\Roaming\Typora\typora-user-images\image-20220901160436668.png)]

在这个过程中会产生很多个区间，所以我们需要动态维护一下区间的信息。如上图，初始时，只有1个区间[0, n - 1]，第一轮删数后，变成2个区间[0, a - 1]，[a + 1, n - 1]；第二轮删数后，变成3个区间[0, b - 1]，[b + 1, a - 1]，[a + 1, n - 1]，以此类推。

我们在每一轮，维护所有区间内的和，选出其中最大者最为该一轮的答案；随后进行删数，删数后对区间信息进行更新即可。

对于求解一个区间的和，可以简单的用前缀和来处理。但每一轮删数时，我们需要确定要删除的这个位置，位于哪一段区间，随后将那段区间一分为二，将原区间的和移除，并加入新产生的两段区间的和，并更新区间信息。

• 对于维护所有区间和中的最大者，我们可以用大根堆来实现，Java中可以直接使用PriorityQueue，但注意它默认是小根堆，需要额外设置一下比较函数。
• 对于每次删某一个位置的数，我们需要确定这个位置位于哪个区间。这个过程可以用二分来做，我们用一个数组维护所有区间，并按照区间右端点从小到大排序。当给定需要删除的位置x后，我们对这个区间数组进行二分查找，找到第一个右端点 >= x 的区间，这个区间就是x所在的区间。

按照这个思路，写出代码如下（先贴周赛当晚的代码）

class Solution {
	public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
		int n = nums.length;

		long[] preSum = new long[n + 1];
		for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + nums[i - 1];

		List<int[]> segment = new LinkedList<>();
		segment.add(new int[]{0, n - 1});

		long[] ans = new long[n];

		// 按最大的来
		PriorityQueue<Long> queue = new PriorityQueue<>((o1, o2) -> (int) (o2 - o1));
		queue.offer(preSum[n]);

		for (int i = 0; i < n; i++) {
			int idx = removeQueries[i];
			// 找到这个区间
			int u = find(segment, idx);
			//  找到区间的左右端点
			int l = segment.get(u)[0];
			int r = segment.get(u)[1];
			// 计算这个要被拆分的区间的区间和
			long sumToRemove = preSum[r + 1] - preSum[l];
			queue.remove(sumToRemove);
			// 从区间中移除
			segment.remove(u);
			// [l, idx - 1]  [idx + 1, r]
			long leftSum = preSum[idx] - preSum[l];
			long rightSum = preSum[r + 1] - preSum[idx + 1];
			if (leftSum > 0) queue.offer(leftSum);
			if (rightSum > 0) queue.offer(rightSum);
			insertSegment(segment, l, idx - 1);
			insertSegment(segment, idx + 1, r);
			ans[i] = queue.isEmpty() ? 0L : queue.peek();
		}
		return ans;
	}

	private void insertSegment(List<int[]> segment, int l, int r) {
		if (l > r) return ;
		int[] s = new int[]{l, r};
		// 找到第一个右端点大于等于它的, 插入
		int i = 0, j = segment.size() - 1;
		while (i < j) {
			int mid = i + j >> 1;
			if (segment.get(mid)[1] >= r) j = mid;
			else i = mid + 1;
		}
		if (i == segment.size() - 1 && segment.get(i)[1] < r) {
			segment.add(s);
		} else {
			segment.add(i, s);
		}
	}

	private int find(List<int[]> segment, int i) {
		// 按右端点从小到达排序, 找到第一个右端点 >= i的
		int n = segment.size();
		int l = 0, r = n - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (segment.get(mid)[1] >= i) r = mid;
			else l = mid + 1;
		}
		return l;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

当时只过了24个样例，就没有后续了

今天重新回顾，把WA的样例拿出来自己本地debug了下。发现是定义PriorityQueue时，比较函数的设置有点问题，周赛当晚的代码中，是这样定义的：

PriorityQueue queue = new PriorityQueue<>((o1, o2) -> (int) (o2 - o1));

根据WA的样例数据的debug结果，使用这个PriorityQueue进行如下操作，最后peek查看堆顶时，返回的并不是最大值

offer : 13515314767
remove : 13515314767
offer : 11940603404
offer : 1567686020
remove : 11940603404
offer : 7895194880
offer: 4042112186
peek : 此时堆中有1567686020，7895194880，4042112186；应当返回的最大值是7895194880，而实际返回的是4042112186

这是因为堆中存的是long，但是比较函数中进行了截断(int) (o2 - o1)。当时那样写仅仅是因为Comparator接口定义的返回值是int

修改下PriorityQueue的定义：PriorityQueue queue = new PriorityQueue<>((o1, o2) -> o1 < o2 ? 1 : o1 == o2 ? 0 : -1);

就能避免这种错误。

也可以简单这样来定义：PriorityQueue queue = new PriorityQueue<>(Comparator.reverseOrder());

这样修改后再尝试提交，得到TLE

至少证明俺周赛当晚的思路是没问题的，只是时间复杂度上差了一些。（苦笑.jpg）

先算一下上面解法的时间复杂度，构造前缀和需要$O(n)$，每次从所有区间中定位某个位置所属区间，使用了二分，复杂度为$O(nlogn)$，总时间复杂度应该是$O(nlogn)$的呀，题目的数据范围也就是10^5，这个范围只有达到$O(n^2)$才会超时才对呀。咋回事呢？！每次操作需要调整堆，每次调整也是$O(logn)$，调整n次也是$O(nlogn)$呀，每次还要对新的区间进行插入，上面的代码再插入区间时也用了二分，会不会是因为时间复杂度前面的常数项太高了导致的？

仔细想来，每次插入新产生的区间时，不需要再查找插入位置的，直接在原先位置进行插入就好了，那么来试一下看看。

class Solution {
    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;

        long[] preSum = new long[n + 1];
        for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + nums[i - 1];

        List<int[]> segment = new LinkedList<>();
        segment.add(new int[]{0, n - 1});

        long[] ans = new long[n];

        // 按最大的来
        PriorityQueue<Long> queue = new PriorityQueue<>((o1, o2) -> o1 < o2 ? 1 : o1 == o2 ? 0 : -1);
        queue.offer(preSum[n]);

        for (int i = 0; i < n; i++) {
            int idx = removeQueries[i];
            // 找到这个区间
            int u = find(segment, idx);
            //  找到区间的左右端点
            int l = segment.get(u)[0];
            int r = segment.get(u)[1];
            // 计算这个要被拆分的区间的区间和
            long sumToRemove = preSum[r + 1] - preSum[l];
            queue.remove(sumToRemove);
            // 从区间中移除
            segment.remove(u);
            // [l, idx - 1]  [idx + 1, r]
            long leftSum = preSum[idx] - preSum[l];
            long rightSum = preSum[r + 1] - preSum[idx + 1];
            if (leftSum > 0) queue.offer(leftSum);
            if (rightSum > 0) queue.offer(rightSum);
            // 插入2个新的区间到原位置
            insertSegment(segment, l, idx - 1, idx + 1, r, u);
            ans[i] = queue.isEmpty() ? 0L : queue.peek();
        }
        return ans;
    }

    private void insertSegment(List<int[]> segment, int l1, int r1, int l2, int r2, int i) {
        boolean leftAdd = false;
        if (l1 <= r1) {
            int[] s = new int[]{l1, r1};
            if (i >= segment.size()) segment.add(s);
            else segment.add(i, s);
            leftAdd = true;
        }
        if (l2 <= r2) {
            int[] s = new int[]{l2, r2};
            i = leftAdd ? i + 1 : i; //若第一个区间插入了, 则第二个区间插入的位置往后挪一位
            if (i >= segment.size()) segment.add(s);
            else segment.add(i, s);
        }
        
    }

    private int find(List<int[]> segment, int i) {
        // 按右端点从小到达排序, 找到第一个右端点 >= i的
        int n = segment.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (segment.get(mid)[1] >= i) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

提交后发现仍然TLE（后续补充：最后发现可能是两个原因：

1. 每次对区间进行切割时，会调用PriorityQueue的remove方法移除一个元素（移除被切割的那个区间的和），这个方法是通过遍历堆中所有元素来实现的，是线性复杂度$O(n)$

2. 每次对区间进行分割时，会从维护区间的数组中移除某个区间，在数组中移除某个位置，会使得后面的位置也要一起挪动，也是线性复杂度$O(n)$

3. 再加上外层循环，一共n次切割，总的复杂度就已经达到$O(n^2)$了

   ）

此时俺点开题解，看看各位优秀的人才是怎么解答这道题的。

正解

上面俺的思路是正向做的，这道题可以正向做，也可以反向做。反向做就是从最后一个数字开始，依次把数字加回去。

正向做思路稍微麻烦一些，大体思路就是我上面的思路，但有一些不一样的地方。

反向做就简单一些，直接用并查集做集合合并，并维护每个集合的和即可，并且并查集可以将时间复杂度降低到$O(n)$。

倒序做，并查集做法：

/**
** 9ms
**/
class Solution {

    int[] p;  // 并查集 parent 数组
    
    long[] sum; // 每个集合的和
    
    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;
        p = new int[n];
        sum = new long[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;  // 初始时每个点都是单独成为一个集合
            sum[i] = nums[i];
        }
        boolean[] st = new boolean[n]; // 某个点是否被添加过
        long[] ans = new long[n];
        long t = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = removeQueries[i];
            if (x > 0 && st[x - 1]) {
                // 若左侧相邻点已被添加, 则合并
                merge(x, x - 1);
            }
            if (x < n - 1 && st[x + 1]) {
                // 若右侧相邻点已被添加, 则合并
                merge(x, x + 1);
            }
            st[x] = true; // 标记当前点已被添加
            ans[i] = t; // 先将t赋值给答案ans数组, 再更新t
            t = Math.max(t, sum[find(x)]); // 合并结束后, 用该点所属的集合的子段和, 来更新t, 本轮循环得到的t, 是下一轮的答案
        }
        return ans;
    }

    private int find(int x) {
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    private void merge(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return ; // no need to merge
        p[px] = py; // 将px合并到py上去
        sum[py] += sum[px];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

正序做，前缀和+动态维护区间

和我自己的思路不同，这份正序做的代码，没有维护当前存在的那些区间[l,r]，而是维护切割点，即每次从哪个位置进行了切割。然后借用TreeSet这种结构，来维护切割点的有序性，并调用lower和higher函数来进行查找，可以对于指定一个点idx，找到其左侧第一个切割点，和右侧第一个切割点，于是就能得到idx所属的区间（两个切割点之间没有被切割，就是一个完整区间）。

/**
** 1397ms, 差点超时
**/
class Solution {
    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;

        long[] preSum = new long[n + 1];
        for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + nums[i - 1];

        // 存放切割的点
        TreeSet<Integer> idxSet = new TreeSet<>();
        // 处理边界情况
        idxSet.add(-1); 
        idxSet.add(n);

        long[] ans = new long[n];

        // 按最大的来
        PriorityQueue<Long> queue = new PriorityQueue<>(Comparator.reverseOrder());
        queue.offer(preSum[n]);

        for (int i = 0; i < n; i++) {
            int idx = removeQueries[i];
            // 找到idx所属的区间
            int l = idxSet.lower(idx) + 1, r = idxSet.higher(idx) - 1;
            // 计算这个要被拆分的区间的区间和
            long sumToRemove = preSum[r + 1] - preSum[l];
            queue.remove(sumToRemove); // 这里remove的时间复杂度比较高, 查看PriorityQueue源码发现会遍历全部元素
            // 从区间中移除
            // [l, idx - 1]  [idx + 1, r]
            long leftSum = preSum[idx] - preSum[l];
            long rightSum = preSum[r + 1] - preSum[idx + 1];
            if (leftSum > 0) queue.offer(leftSum);
            if (rightSum > 0) queue.offer(rightSum);
            idxSet.add(idx);
            ans[i] = queue.isEmpty() ? 0L : queue.peek();
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

上面的正序代码，由于每次进行切割时，会调用remove方法从PriorityQueue中移除一个元素，而这个操作是通过遍历完成的，时间复杂度很高。我们尝试不进行移除。而采用惰性删除。

/**
** 489ms
**/
class Solution {
    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int n = nums.length;

        long[] preSum = new long[n + 1];
        for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + nums[i - 1];

        TreeSet<Integer> cutPointSet = new TreeSet<>();
        cutPointSet.add(-1);
        cutPointSet.add(n);

        long[] ans = new long[n];

        // 按和最大的来
        PriorityQueue<long[]> queue = new PriorityQueue<>((o1, o2) -> Long.compare(o2[0], o1[0]));
        // 同时存下该和对应的区间
        queue.offer(new long[] { preSum[n], 0, n - 1});

        for (int i = 0; i < n; i++) {
            int idx = removeQueries[i];
            // 找到idx所属的区间, 从切割点中找到第一个小于idx的数(从idx往左找), 加上1就是idx所属区间的左端点
            // 同理找到第一个大于idx的数(从idx往右找), 减去1就是区间右端点
            // 其实由于每次新的切割点都是不同的，所以对于每次的idx，cutPointSet中一定不存在
            // 所以下面的lower(<)函数可以换成floor(<=), higher(>)也可以换成ceiling(>=)
            int l = cutPointSet.lower(idx) + 1, r = cutPointSet.higher(idx) - 1;
            // 新插入一个切割点进去
            cutPointSet.add(idx);
            // [l, idx - 1]  [idx + 1, r]
            // 该区间被切割成2个新的区间, 看下新区间长度是否为0 (是否能真正形成一个区间)
            if (l <= idx - 1) queue.offer(new long[] {preSum[idx] - preSum[l], l, idx - 1});
            if (idx + 1 <= r) queue.offer(new long[] {preSum[r + 1] - preSum[idx + 1], idx + 1, r});
            while (!queue.isEmpty()) {
                // 取和最大的元素
                long[] t = queue.peek();
                int a = (int) t[1], b = (int) t[2];
                // 判断一下[a,b]这个区间是否有效, 若无效则删除之, 判断依据是看[a,b]中间是否存在切割点
                int ca = cutPointSet.ceiling(a); // 从切割点集合中找到 >= a 的第一个数
                int cb = cutPointSet.floor(b); // 从切割点集合中找到 <= b 的第一个数
                // 注意需要取=, 因为端点本身是切割点也会使得[a,b]无效
                if (ca <= b || cb >= a) {
                    // 若[a,b]之间存在切割点, 则区间中间存在切割点, 对该区间进行惰性删除
                    queue.poll();
                    continue;
                }
                // 找到有效区间
                ans[i] = t[0];
                break;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

总结

仍然是3道题，第4题做了尝试，有基本思路（不像以前根本没时间和机会和第4题打照面），还算是有进步。什么时候能AK一次呢，还得继续加油。