【LeetCode】3356、零数组变换 II

一、数据结构-差分-一维差分、二分

1.1 数据结构-差分-一维差分、二分

1.1.1 题意复述

题意复述: 有 nums[] 数组(如 [2, 0, 2]), 有 queries[] 数组(如 [[0,2,1], [0,2,1], [1,1,3]])

遍历 queries, 对每个 queries[i] 为 [li, ri, vali]
可以把 介于 nums[li…ri] 的元素的子集, 减去 [0…vali] 的数

问最终需操作几个 queries[], 可使 nums[] 全部变为 0. 记答案为 k(即操作的是 queries[0…k])

1.1.2 思路

因为操作的是 nums[li…ri] 的【子集】, 且减小的数 【最多】为 vali, 所以 k【越多越好】.
即 k 越多, 越满足答案. 【具备单调性】, 所以可用 【二分法】.

二分法: 是指, 从 queries[] 数组的长度的二分, 即 queries[0…len(queries)] 中 k 从 i = 0, j = len(queries) 的 二分.
二分的 check() 函数, 即为 【LeetCode 3355】 的过程.
最终返回二分的 k 即可.

二分法的注意: 用 开区间 确实更容易写边界条件

1. 没有 +1 或 -1 的判断
2. 最后返回的值 肯定是 l 或 r, 只需根据 二分的分支 确定 l 的含义, r 的含义, 即可

1.1.3 手写二分

// go
func minZeroArray(nums []int, queries [][]int) int {n := len(nums)check := func(k int) bool {d := make([]int, n+1) // 差分数组for _, q := range queries[:k] { // k锁定了queries[]的前k项start, end, val := q[0], q[1], q[2]d[start]+=vald[end+1]-=val}now := 0for i := range n {now += d[i]if now < nums[i] {return false}}return true}q := len(queries)l, r := -1, q+1 // 左开右开区间for l + 1 < r {m := l + (r-l)>>1if check(m) {r = m // m 已经符合, 但为了找更小的, 再向左找} else {l = m // 不符合, 则需找更大的(向右找), 因为k越大越符合题意}}if r <= q {return r // 因为二分中 check(m) 符合时, r 为 m. 所以最终返回的 r 就是符合题意的}return -1 // r == q+1
}

1.1.4 sort.Search() 二分

func minZeroArray(nums []int, queries [][]int) int {n := len(nums)check := func(k int) bool {d := make([]int, n+1) // 差分数组for _, q := range queries[:k] { // k锁定了queries[]的前k项start, end, val := q[0], q[1], q[2]d[start]+=vald[end+1]-=val}now := 0for i := range n {now += d[i]if now < nums[i] {return false}}return true}q := len(queries)ans := sort.Search(q+1, func(k int) bool { // sort.Search() 是找第一个 true 的下标return check(k)})if ans <= q {return ans}return -1 // r == q+1
}

1.1.5 sort.Find() 二分

func minZeroArray(nums []int, queries [][]int) int {n := len(nums)check := func(k int) bool {d := make([]int, n+1) // 差分数组for _, q := range queries[:k] { // k锁定了queries[]的前k项start, end, val := q[0], q[1], q[2]d[start]+=vald[end+1]-=val}now := 0for i := range n {now += d[i]if now < nums[i] {return false}}return true}q := len(queries)// 因为 sort.Search() 是找第一个 f() == true 的下标, 而 sort.Find() 是找第一个 f() <= 0 的下标, 所以此处定义 sort.Find() 的 f 为 if check(k) {return 0}ans, found := sort.Find(q+1, func(k int) int { // sort.Find() 是找第一个 f() <= 0 的下标if check(k) {return 0 // <= 0}return 1})if found {return ans}return -1 // r == q+1
}

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts