本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。
T1. 找出最大的可达成数字（Easy）
- 标签：模拟
T2. 达到末尾下标所需的最大跳跃次数（Medium）
- 标签：动态规划、动态开点线段树
T3. 构造最长非递减子数组（Medium）
- 标签：动态规划
T4. 使数组中的所有元素都等于零（Medium）
- 标签：贪心、差分数组、前缀和
T1. 找出最大的可达成数字（Easy）
https://leetcode.cn/problems/find-the-maximum-achievable-number/
题解（模拟）
简单模拟题，在每一轮操作中可以将 num 加一，而对 x 减一，因此最大 x 就是 num + 2 * t。
class Solution {
fun theMaximumAchievableX(num: Int, t: Int): Int {
return num + 2 * t
}
}
复杂度分析：
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
T2. 达到末尾下标所需的最大跳跃次数（Medium）
https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index
题解一（动态规划）
与 「55. 跳跃游戏」 类似，但本题中每次操作可以跳转到的位置需要满足 nums[j] - nums[i] ≤ target，而跳跃游戏中可跳转的位置是 [i - nums[i], i + nums[i]]，且每次只能向右跳（j > i）。容易想到，对于位置 nums[i] 来说，必然存在从 nums[0, i - 1] 中的某个位置跳转得来，即 dp[i] = dp[j] + 1，可以用动态规划实现。
class Solution {
fun maximumJumps(nums: IntArray, target: Int): Int {
// 跳转到差值绝对值不大于 target 的位置，不能返回
val n = nums.size
val dp = IntArray(n) { -1 }
dp[0] = 0
for (j in 1 until n) {
for (i in 0 until j) {
// 寻找合法子问题
if (-1 != dp[i] && Math.abs(nums[j] - nums[i]) <= target) {
dp[j] = Math.max(dp[j], dp[i] + 1)
}
}
}
return dp[n - 1]
}
}
复杂度分析：
- 时间复杂度：$O(n^2)$ 总共有 n 个状态，每个状态需要枚举 $O(n)$ 个状态，因此整体时间复杂度是 $O(n^2)$；
- 空间复杂度：$O(n)$ DP 数组空间。
题解二（动态开点线段树）
在题解一中，当枚举到每个元素 nums[i] 时，我们检查前驱元素中区间范围为 [nums[i] - target, nums[i] - target] 范围内的元素的最大跳转次数 j，使得 dp[i] = dp[j] + 1，这个过程可以抽象为两个动作：
- 单点更新：dp[nums[i]] = 子状态 + 1
- 区间查询：子状态 = max{nums[i] - k, nums[i] - 1}
这是一个涉及单点更新和区间查询的数据结构，可以使线段树（基于值域）实现，同时这与 「2407. 最长递增子序列 II」 问题是类似的。另外，由于输入数据值域非常大，我们需要先离散化或使用动态开点线段树，这里使用动态开点的方法。
class Solution {
fun maximumJumps(nums: IntArray, target: Int): Int {
// 值域线段树（动态开点）
val tree = SegementTree(-1e9.toLong(), 1e9.toLong())
tree.set(0L + nums[0], 0)
for (i in 1 until nums.size) {
val step = tree.query(0L + nums[i] - target, 0L + nums[i] + target) + 1 // 区间查询
tree.set(0L + nums[i], step) // 单点更新
if (i == nums.size - 1) return if (step < 0) -1 else step // 终点
}
return -1
}
// 动态开点线段树（单点更新没必要做 Lazy）
private class SegementTree(private val from: Long, private val to: Long) {
// 线段树根节点
private val root = Node(from, to, Integer.MIN_VALUE)
// 线段树节点（区间范围与区间最值）
private class Node(val left: Long, val right: Long, var value: Int) {
// 中位索引
val mid : Long get() = (left + right) shr 1 // 存在负数，不能使用无符号右移
// 左子树
val l by lazy { Node(left, mid, Integer.MIN_VALUE) }
// 右子树
val r by lazy { Node(mid + 1, right, Integer.MIN_VALUE) }
// 单点更新
fun set(pos: Long, value: Int) {
// println("[$left, $right] set=[$pos, $value]")
// 1、当前节点不处于区间范围内
if (left > pos || right < pos) return
// 2、叶子节点
if (left == right) {
this.value = Math.max(this.value, value)
return
}
// 3、更新左子树
if (pos <= mid) l.set(pos, value)
// 4、更新右子树
if (pos > mid) r.set(pos, value)
// 5、合并子节点的结果
this.value = Math.max(l.value, r.value)
}
// 区间查询
fun query(from: Long, to: Long): Int {
// println("[$left, $right] query[$from, $to]")
// 1、当前节点不处于区间范围内
if (this.left > to || this.right < from) return Integer.MIN_VALUE
// 2、当前节点完全处于区间范围之内
if (this.left >= from && this.right <= to) return value
// 3、合并子节点的结果
return Math.max(l.query(from, to), r.query(from, to))
}
}
// 单点更新
fun set(pos: Long, value: Int) {
root.set(pos, value)
}
// 区间查询
fun query(from: Long, to: Long): Int {
return root.query(from, to)
}
}
}
复杂度分析：
- 时间复杂度：$O(nlgU)$ 每次查询操作 $O(lgU)$ 整体的时间复杂度是 $O(nlgU)$；
- 空间复杂度：$O(n)$ 散列表空间
T3. 构造最长非递减子数组（Medium）
https://leetcode.cn/problems/longest-non-decreasing-subarray-from-two-arrays/
题解一（动态规划）
讨论区多少人看成 LIS 最长递增子序列问题了呢？
对于每个位置 i，当且仅有选择 num1[i] 或 nums2[i] 两种选择，需要思考「选哪个」。
我们定义 dp[i][0/1] 表示以 i 位置为结尾的最长非递减子数组，那么对于位置 i 来说，有 2 种选择：
- 如果 nums1[i] 能够与 nums1[i - 1] 和 nums2[i - 2] 构造非递减子序列，那么可以构造更长的子数组，dp[i][0] = max{dp[i-1][0], dp[i-1][1]} + 1；
- 如果 nums2[i] 能够与 nums1[i - 1] 和 nums2[i - 2] 构造非递减子序列，那么可以构造更长的子数组，dp[i][1] = max{dp[i-1][0], dp[i-1][1]} + 1；
- 否则，dp[i][0] = dp[i][1] = 1
class Solution {
fun maxNonDecreasingLength(nums1: IntArray, nums2: IntArray): Int {
val n = nums1.size
val dp = Array(n) { IntArray(2) { 1 } }
var ret = 1
for (i in 1 until n) {
val x = nums1[i]
val y = nums2[i]
if (nums1[i] >= nums1[i - 1]) {
dp[i][0] = Math.max(dp[i][0], dp[i - 1][0] + 1)
}
if (nums1[i] >= nums2[i - 1]) {
dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] + 1)
}
if (nums2[i] >= nums1[i - 1]) {
dp[i][1] = Math.max(dp[i][1], dp[i - 1][0] + 1)
}
if (nums2[i] >= nums2[i - 1]) {
dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] + 1)
}
ret = Math.max(ret, dp[i][0])
ret = Math.max(ret, dp[i][1])
}
return ret
}
}
复杂度分析：
- 时间复杂度：$O(n)$ 总共有 n 个子问题，每个子问题需要枚举 4 个子状态，整体的时间复杂度是 $O(n)$；
- 空间复杂度：$O(n)$ DP 数组空间。
题解二（动态规划 + 滚动数组）
由于 dp[i] 只会利用 dp[i - 1] 的信息，我们可以使用滚动数组优化空间复杂度：
class Solution {
fun maxNonDecreasingLength(nums1: IntArray, nums2: IntArray): Int {
val n = nums1.size
var dp = IntArray(2) { 1 }
var ret = 1
for (i in 1 until n) {
val x = nums1[i]
val y = nums2[i]
val newDp = IntArray(2) { 1 }
if (nums1[i] >= nums1[i - 1]) {
newDp[0] = Math.max(newDp[0], dp[0] + 1)
}
if (nums1[i] >= nums2[i - 1]) {
newDp[0] = Math.max(newDp[0], dp[1] + 1)
}
if (nums2[i] >= nums1[i - 1]) {
newDp[1] = Math.max(newDp[1], dp[0] + 1)
}
if (nums2[i] >= nums2[i - 1]) {
newDp[1] = Math.max(newDp[1], dp[1] + 1)
}
ret = Math.max(ret, newDp[0])
ret = Math.max(ret, newDp[1])
dp = newDp
}
return ret
}
}
复杂度分析：
- 时间复杂度：$O(n)$ 总共有 n 个子问题，每个子问题需要枚举 4 个子状态，整体的时间复杂度是 $O(n)$；
- 空间复杂度：$O(1)$ DP 数组空间。
T4. 使数组中的所有元素都等于零（Medium）
https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/
题解一（贪心）
这道题在周赛 T4 题中算很简单的题目了，放在 T2 比较合适。
我们发现窗口 K 是固定的，同时对于数组的首部或尾部元素来说，它们的约束是最强的，即：只能被从 nums[0] 为起点或 nums[n-1] 为终点的窗口消除。因此，为了实现将数组中所有元素重置为零的目标，我们从左到右找到第一个不为 0 的元素 nums[i] 为起点开始消除：
- nums[i] == 0，跳过；
- nums[i] < 0，不满足，说明在 nums[0, i - 1] 区间必然存在一个较大的整数导致 nums[i] 被过渡消除；
- nums[i] > 0，如果 i > nums.size - k，那么无法构造出长为 k 的窗口，不满足；否则将 nums[i,i +k - 1] 的窗口减去 nums[i]。
class Solution {
fun checkArray(nums: IntArray, k: Int): Boolean {
for ((i, x) in nums.withIndex()) {
if (x == 0) continue
if (x < 0 || i > nums.size - k) return false
for (j in i until i + k) {
nums[j] -= x
}
}
return true
}
}
复杂度分析：
- 时间复杂度：$O(n^2)$ 最坏情况下取 k = n/2，而 nums 数组为 [1,2,3,4,5…] 递增序列，那么时间复杂度是 $O(n^2/4)$；
- 空间复杂度：$O(1)$ 仅使用常量级别空间。
题解二（差分数组）
题解一中的每次对操作相当于做区间更新，可以使用差分数组（使用标记代替减法操作）来优化时间复杂度：
- 区间更新：对于区间在 nums[i, i + k - 1] 的元素减去 nums[i]，则对 diff[i+k] += nums[i]，而对 diff[i] -= nums[i]，时间复杂度是 O(n)；
- 查询单点值：对于 nums[i] 的实际值的常规做法是求 diff[i] 的前缀和，时间复杂度是 O(n)，这是无法满足要求的。
// 超出时间限制
class Solution {
fun checkArray(nums: IntArray, k: Int): Boolean {
val n = nums.size
// 差分数组
val diff = IntArray(n + 1)
for (i in 0 until nums.size) {
// 从差分数组还原真实值（求前缀和）
var x = nums[i]
for (j in 0 .. i) {
x += diff[j] // (存在重复计算)
}
if (x < 0) return false
if (x == 0) continue
if (i > nums.size - k) return false
// 区间更新
diff[i] -= x
diff[i + k] += x
}
return true
}
}
复杂度分析：
- 时间复杂度：$O(n^2)$ 在内层循环中，需要计算差分数组的前缀和还原数组值，整体时间复杂度是 $O(n^2)$；
- 空间复杂度：$O(n)$ 差分数组空间。
题解三（差分数组 + 线性扫描）
由于我们是从左向右枚举数组元素，我们可以在做从左向右执行区间更新时，边维护差分数组的前缀和。
class Solution {
fun checkArray(nums: IntArray, k: Int): Boolean {
val n = nums.size
// 差分数组
val diff = IntArray(n + 1)
// 差分前缀和
var diffSum = 0
for (i in 0 until nums.size) {
// 边更新边维护差分数组的前缀和
diffSum += diff[i]
val x = nums[i] + diffSum
if (x == 0) continue
if (x < 0 || i > nums.size - k) return false
// 区间更新
diff[i] -= x
diff[i + k] += x
diffSum -= x
}
return true
}
}
复杂度分析：
- 时间复杂度：$O(n)$ 只需要一趟线性扫描；
- 空间复杂度：$O(n)$ 差分数组空间。
