第 444 场周赛-20250406
https://leetcode.cn/contest/weekly-contest-444/
中国时间：2025-04-06 10:30, 1 小时 30 分
3507.移除最小数对使数组有序I
简单，https://leetcode.cn/problems/minimum-pair-removal-to-sort-array-i/
3508.设计路由器
中等，https://leetcode.cn/problems/implement-router/
3509.最大化交错和为K的子序列乘积
困难，https://leetcode.cn/problems/maximum-product-of-subsequences-with-an-alternating-sum-equal-to-k/
给你一个整数数组 nums 和两个整数 k 与 limit，你的任务是找到一个非空的 子序列，满足以下条件：
- 它的 交错和 等于
k。 - 在乘积 不超过
limit的前提下，最大化 其所有数字的乘积。
返回满足条件的子序列的 乘积 。如果不存在这样的子序列，则返回 -1。
子序列 是指可以通过删除原数组中的某些（或不删除）元素并保持剩余元素顺序得到的新数组。
交错和 是指一个 从下标 0 开始 的数组中，偶数下标 的元素之和减去 奇数下标 的元素之和。
示例 1：
输入： nums = [1,2,3], k = 2, limit = 10
输出： 6
解释：
交错和为 2 的子序列有：
[1, 2, 3]- 交错和：
1 - 2 + 3 = 2 - 乘积：
1 * 2 * 3 = 6
- 交错和：
[2]- 交错和：2
- 乘积：2
在 limit 内的最大乘积是 6。
示例 2：
输入： nums = [0,2,3], k = -5, limit = 12
输出： -1
解释：
不存在交错和恰好为 -5 的子序列。
示例 3：
输入： nums = [2,2,3,3], k = 0, limit = 9
输出： 9
解释：
交错和为 0 的子序列包括：
[2, 2]- 交错和：
2 - 2 = 0 - 乘积：
2 * 2 = 4
- 交错和：
[3, 3]- 交错和：
3 - 3 = 0 - 乘积：
3 * 3 = 9
- 交错和：
[2, 2, 3, 3]- 交错和：
2 - 2 + 3 - 3 = 0 - 乘积：
2 * 2 * 3 * 3 = 36
- 交错和：
子序列 [2, 2, 3, 3] 虽然交错和为 k 且乘积最大，但 36 > 9，超出 limit 。下一个最大且在 limit 范围内的乘积是 9。
提示：
1 <= nums.length <= 1500 <= nums[i] <= 12-105 <= k <= 1051 <= limit <= 5000
3510.移除最小数对使数组有序II
doubly-linked list + heap, https://leetcode.cn/problems/minimum-pair-removal-to-sort-array-ii/