问题描述

给定一个大小为 n 的非负整数数组 nums，我们需要通过若干次操作将数组中的所有元素变为 0。每次操作可以选择一个子数组 [i, j]，将该子数组中所有最小的非负整数设为 0。目标是找到使整个数组变为 0 所需的最少操作次数。

关键思路

经过分析，发现这个问题可以通过单调栈高效解决。核心思路是：

  • 维护一个单调递减栈，栈中元素表示需要单独处理的不同数值

  • 当遇到比栈顶元素小的数字时，需要先处理掉栈顶元素（弹出并计数）

  • 最终栈中剩余的元素也需要各自处理

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        stack = []  # 单调递减栈
        operations = 0  # 操作计数器
        
        for num in nums:
            # 当栈不为空且栈顶元素大于当前元素时
            while stack and stack[-1] > num:
                operations += 1  # 需要一次操作来处理栈顶元素
                stack.pop()  # 弹出栈顶元素
            
            # 如果当前元素不为0，且满足入栈条件，则压入栈中
            if num and (not stack or stack[-1] != num):
                stack.append(num)
        
        # 栈中剩余元素也需要操作
        operations += len(stack)
        
        return operations

算法步骤详解

  1. 初始化：创建一个空栈和一个操作计数器

  2. 遍历数组：对于每个元素：

    • 如果栈不为空且栈顶元素大于当前元素，弹出栈顶并增加操作计数

    • 如果当前元素不为0且满足入栈条件（栈为空或栈顶不等于当前元素），将其压入栈中

  3. 处理剩余元素：将栈中剩余元素的数量加到操作计数中

  4. 返回结果：返回总操作次数