← 返回 uber 的题目列表Zero Array After Ordered Range Decrements (Independent Per Index)
类型:online_judge
Problem (Coding)
You are given a non-negative integer array nums of length n and a 2D integer array queries, where queries[i] = [li, ri, vali].
You must process the queries in order, from queries[0] to queries[m-1].
For each query [li, ri, vali], you may perform the following operation for every index j such that li <= j <= ri:
Choose an integer dec[j] with 0 <= dec[j] <= vali.
Decrease nums[j] by dec[j] (the chosen decrement can be independent for each index).
After the operation (and at all times), all values must remain non-negative.
Return true if it is possible to make nums become an all-zero array after processing all queries; otherwise return false.
Constraints (reasonable interview setting)
1 <= n, m <= 2 * 10^5
0 <= nums[i] <= 1e9
0 <= li <= ri < n
0 <= vali <= 1e9
Example
Input
nums = [1,0,1]
queries = [[0,2,1]]
Output
true
Explanation For query [0,2,1]:
Decrease nums[0] by 1
Decrease nums[2] by 1
Keep nums[1] unchanged Result is [0,0,0].
Example
Input
3
1 0 1
1
0 2 1
Output
true