3542. Minimum Operations to Convert All Elements to Zero
Approach
Monotonic stack; pop when current value > 0 and ≤ stack top; count non-zero pops.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Simulation problems require implementing the described process step by step. Focus on correctly handling edge cases and state transitions. Common in geometry, game problems, and string manipulation. Optimize only if the naive simulation exceeds the time limit.
// Approach: Monotonic stack; pop when current value > 0 and ≤ stack top; count non-zero pops.
// Time: O(n) Space: O(n)
public class Solution
{
public int MinOperations(int[] nums)
{
int ans = 0;
Stack<int> stack = new Stack<int>();
stack.Push(0);
foreach (int num in nums)
{
while (stack.Count > 0 && stack.Peek() > num)
stack.Pop();
if (stack.Count == 0 || stack.Peek() < num)
{
++ans;
stack.Push(num);
}
}
return ans;
}
}