307 周赛t4/85 双周赛t4复盘 6155/6159

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

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

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

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

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

示例 1：

输入：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] 。

示例 2：

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

提示：

• n == nums.length == removeQueries.length
• 1 <= n <= 1e5
• 1 <= nums[i] <= 1e9
• 0 <= removeQueries[i] < n
• removeQueries 中所有数字 互不相同 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-segment-sum-after-removals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 做题结果

成功，倒序并查集。开始蒙了一阵，后面突然想到，之前写过类似的。

方法：并查集

1. 这个并查集也有点变化，初始父节点先选-1

2. 初始和为0，大小为0

3. 按照移除顺序，反向加入节点

4. 加入节点时，将当前的节点位置，大小，和初始赋值

5. 如果存在左右方向的元素已经加入并查集（父节点非-1），可进行链接，注意这里有个变动，是需要把和放到父节点

6. 前一个元素返回和与后续和的较大值

class Solution {
        int[] parent;
        int[] sizes;
        long[] sums;
 
        public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
            int n = nums.length;
            parent = new int[n];
            Arrays.fill(parent,-1);
            sizes = new int[n];
            sums = new long[n];
 
            long[] ans = new long[n];
            for(int i = n-1; i>=1; i--){
                int j = removeQueries[i];
                parent[j]=j;
                sizes[j]=1;
                sums[j]=nums[j];
                long v = sums[j];
                if(j>0&&parent[j-1]!=-1){
                    v = connect(j-1,j);
                }
 
                if(j1 && parent[j+1]!=-1){
                    v = connect(j,j+1);
                }
                ans[i-1]=Math.max(v,ans[i]);
            }
 
            return ans;
        }
 
        private int root(int a){
            while(parent[a]!=a){
                parent[a] = parent[parent[a]];
                a = parent[a];
            }
            return a;
        }
 
        private long connect(int x, int y){
            int rootA = root(x);
            int rootB = root(y);
            if(rootA==rootB) return sums[rootA];
            if(sizes[rootA]>sizes[rootB]){
                sizes[rootA]+=sizes[rootB];
                parent[rootB]=rootA;
                sums[rootA]+=sums[rootB];
                return sums[rootA];
            }else{
                sizes[rootB]+=sizes[rootA];
                parent[rootA]=rootB;
                sums[rootB]+=sums[rootA];
                return sums[rootB];
            }
        }
    }

6155. 找出数组的第 K 大和

给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

注意：空子序列的和视作 0 。

示例 1：

输入：nums = [2,4,-2], k = 5
输出：2
解释：所有可能获得的子序列和列出如下，按递减顺序排列：
- 6、4、4、2、2、0、0、-2
数组的第 5 大和是 2 。

示例 2：

输入：nums = [1,-2,3,4,-10,12], k = 16
输出：10
解释：数组的第 16 大和是 10 。

提示：

• n == nums.length
• 1 <= n <= 1e5
• -1e9 <= nums[i] <= 1e9
• 1 <= k <= min(2000, 2n)

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-k-sum-of-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

失败,没找到正确思路，赛后测试发现，知道正确思路仍然具有一定难度

方法：优先队列（堆）

1. 首先不要想这么复杂，大的不好想，我们想最小的，就最简单全是正数，选择第几小的排列。那一定是空集合[]

2. 把所有元素排序后 [1,2,3]，选择其中的1，是第二小的，于是我们有 [] [1] 

3. 继续到第三个，在这两个的基础上，第三个也可选可不选 [] [1] [1,2]，这样就得到了前k小的和

4. 当前题目是求最大，那么我们可以用 前缀和-元素 做一个 mask来处理。从而达到不用遍历完所有元素，就获得结果的目的

5. 有负数，那么不包含负数的情况，是最大的。负数取反，后续也处理为减法即可

6. 所以就有了大概的思路：排序，按数组顺序依次尝试删除，当新元素在旧元素中删除的前 k 无法在产生影响时退出

class Solution {
        public long kSum(int[] nums, int k) {
            long sum = 0;
            int n = nums.length;
            for(int i = 0; i < n; i++){
                if(nums[i]>=0) sum += nums[i];
                else nums[i]=-nums[i];
            }
 
            PriorityQueue pq = new PriorityQueue<>();
            pq.offer(sum);
            Arrays.sort(nums);
            for (int num : nums) {
                PriorityQueue copy = new PriorityQueue<>(pq);
                boolean change = false;
                while (!copy.isEmpty()){
                    if(pq.size()true;
                    pq.offer(copy.poll() - num);
                    if(pq.size()>k) pq.poll();
                }
                if(!change) break;
            }
 
            return pq.peek();
        }
    }