Π‘ΡΡΠ»ΠΊΠ° Π½Π° Π·Π°Π΄Π°ΡΡ β 3356. Zero Array Transformation II.
π ΠΠΏΠΈΡΠ°Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ
ΠΠ°Π½ ΠΌΠ°ΡΡΠΈΠ² nums
Π΄Π»ΠΈΠ½Ρ N
ΠΈ ΡΠΏΠΈΡΠΎΠΊ Π·Π°ΠΏΡΠΎΡΠΎΠ² queries
, ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΈΠ· ΠΊΠΎΡΠΎΡΡΡ
Π·Π°Π΄Π°ΡΡΡΡ ΠΊΠ°ΠΊ [li, ri, vali]
. ΠΠ°ΠΏΡΠΎΡ ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ, ΡΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Π² Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅ [li, ri]
ΠΌΠΎΠΆΠ½ΠΎ ΡΠΌΠ΅Π½ΡΡΠΈΡΡ Π½Π° Π»ΡΠ±ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΠΎΡ 0
Π΄ΠΎ vali
Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎ Π΄ΡΡΠ³ ΠΎΡ Π΄ΡΡΠ³Π°.
ΠΡΠΆΠ½ΠΎ Π½Π°ΠΉΡΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΠΏΠ΅ΡΠ²ΡΡ
Π·Π°ΠΏΡΠΎΡΠΎΠ² k
, ΠΏΠΎΡΠ»Π΅ ΠΊΠΎΡΠΎΡΡΡ
nums
ΠΌΠΎΠΆΠ΅Ρ ΠΏΡΠ΅Π²ΡΠ°ΡΠΈΡΡΡ Π² ΠΌΠ°ΡΡΠΈΠ², ΡΠΎΡΡΠΎΡΡΠΈΠΉ ΡΠΎΠ»ΡΠΊΠΎ ΠΈΠ· Π½ΡΠ»Π΅ΠΉ. ΠΡΠ»ΠΈ ΡΡΠΎ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ β Π²Π΅ΡΠ½ΡΡΡ -1
.
π‘ ΠΠ΄Π΅Ρ
ΠΠΌΠ΅ΡΡΠΎ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ ΠΈΠ·ΠΌΠ΅Π½ΡΡΡ nums
Π½Π°ΠΏΡΡΠΌΡΡ, Π±ΡΠ΄Π΅ΠΌ Ρ
ΡΠ°Π½ΠΈΡΡ ΠΌΠ°ΡΡΠΈΠ² ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΡΡ
ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ ΠΊ Π΄Π΅ΠΊΡΠ΅ΠΌΠ΅Π½ΡΡ (updates
). ΠΠ½ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π½ΡΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π±Π΅Π· Π»ΠΈΡΠ½ΠΈΡ
Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠΉ.
Π§ΡΠΎΠ±Ρ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°ΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΎΠ±ΡΠ°Π±ΠΎΡΠ°Π½Π½ΡΡ
Π·Π°ΠΏΡΠΎΡΠΎΠ², Π±ΡΠ΄Π΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΆΠ°Π΄Π½ΡΡ ΡΡΡΠ°ΡΠ΅Π³ΠΈΡ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ Π·Π°ΠΏΡΠΎΡΠΎΠ²:
- ΠΠ±ΡΠ°Π±Π°ΡΡΠ²Π°Π΅ΠΌ
nums
ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ
- ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠΎΠ·ΠΈΡΠΈΠΈ
i
, Π΅ΡΠ»ΠΈ nums[i]
Π΅ΡΡ Π½Π΅ ΡΡΠ°Π» 0
, ΠΏΡΡΠ°Π΅ΠΌΡΡ ΠΏΡΠΈΠΌΠ΅Π½ΠΈΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ Π½ΠΎΠ²ΡΡ
Π·Π°ΠΏΡΠΎΡΠΎΠ² ΠΈΠ· ΡΠΏΠΈΡΠΊΠ°.
βοΈ ΠΠ΅ΡΠ°Π»ΠΈ ΠΏΠΎΠ΄Ρ
ΠΎΠ΄Π°
- ΠΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌ ΠΌΠ°ΡΡΠΈΠ²
updates
(N+1
ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ²), Π³Π΄Π΅ updates[i]
Ρ
ΡΠ°Π½ΠΈΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΡΠ΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡ ΠΊ Π΄Π΅ΠΊΡΠ΅ΠΌΠ΅Π½ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ.
- ΠΡΠ΅ΡΠΈΡΡΠ΅ΠΌΡΡ ΠΏΠΎ
nums
, ΠΏΡΠΈΠΌΠ΅Π½ΡΡ Π½Π°ΠΊΠΎΠΏΠ»Π΅Π½Π½ΡΠ΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡ ΠΊ Π΄Π΅ΠΊΡΠ΅ΠΌΠ΅Π½ΡΡ.
- ΠΡΠ»ΠΈ
nums[i]
ΠΎΡΡΠ°ΡΡΡΡ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΠΌ, ΠΆΠ°Π΄Π½ΠΎ Π±Π΅ΡΡΠΌ Π·Π°ΠΏΡΠΎΡΡ ΠΈΠ· ΡΠΏΠΈΡΠΊΠ°.
- ΠΠΎΠ·Π²ΡΠ°ΡΠ°Π΅ΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΡ
Π·Π°ΠΏΡΠΎΡΠΎΠ² ΠΈΠ»ΠΈ
-1
, Π΅ΡΠ»ΠΈ ΠΌΠ°ΡΡΠΈΠ² Π½Π΅ ΡΠ΄Π°Π»ΠΎΡΡ ΠΎΠ±Π½ΡΠ»ΠΈΡΡ.
β³ ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ°
- ΠΡΠ΅ΠΌΡ:
O(N + Q)
, Π³Π΄Π΅ N
β Π΄Π»ΠΈΠ½Π° nums
, Q
β ΡΠΈΡΠ»ΠΎ Π·Π°ΠΏΡΠΎΡΠΎΠ².
- ΠΠ°ΠΆΠ΄ΡΠΉ Π·Π°ΠΏΡΠΎΡ ΠΎΠ±ΡΠ°Π±Π°ΡΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΎΠ΄ΠΈΠ½ ΡΠ°Π· β
O(Q)
.
- ΠΠ°ΠΆΠ΄ΠΎΠ΅
nums[i]
ΠΏΡΠΎΠ²Π΅ΡΡΠ΅ΡΡΡ ΡΠΎΠ²Π½ΠΎ ΠΎΠ΄ΠΈΠ½ ΡΠ°Π· β O(N)
.
- ΠΠ°ΠΌΡΡΡ:
O(N)
, ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΌΠ°ΡΡΠΈΠ² updates
ΠΈΠΌΠ΅Π΅Ρ ΡΠ°Π·ΠΌΠ΅Ρ N+1
.
π» ΠΡΡ
ΠΎΠ΄Π½ΡΠΉ ΠΊΠΎΠ΄
impl Solution {
pub fn min_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
let mut updates = vec![0; nums.len() + 1]; // Tracks decrement changes over the range
let mut queries = queries.into_iter(); // Efficiently consume queries
let mut processed_queries = 0;
let mut accumulated_decrement = 0;
for (i, num) in nums.into_iter().enumerate() {
// Process queries until we can make nums[i] zero
while num > accumulated_decrement + updates[i] {
if let Some(q) = queries.next() {
let (left, right, decrement) = (q[0] as usize, q[1] as usize, q[2]);
if i <= right {
updates[right + 1] -= decrement;
updates[left.max(i)] += decrement;
}
processed_queries += 1;
} else {
return -1; // No more queries left to process
}
}
accumulated_decrement += updates[i];
}
processed_queries
}
}
Tags: #rust #algorithms #greedy