Medium

题目描述

给你一个下标从 0 开始的整数数组 nums。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i]，其中 0 < i < nums.length。

返回使 nums 变为 非递减数组 所需的步数。

示例 1：

输入：nums = [5,3,4,4,7,3,6,11,8,5,11]
输出：3
解释：执行步骤如下：
- 步骤 1：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11]
- 步骤 2：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]  
- 步骤 3：[5,4,7,11,11] 变为 [5,7,11,11]
[5,7,11,11] 是非递减数组。因此，返回 3。

示例 2：

输入：nums = [4,5,7,7,13]
输出：0
解释：nums 已经是非递减数组。因此，返回 0。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

解题思路

这道题的关键在于理解每个元素被移除需要的轮数，答案就是所有元素中被移除轮数的最大值。

核心观察

  1. 一个元素会被移除，当且仅当它左边存在一个严格大于它的元素
  2. 对于每个元素，我们需要计算它被移除需要多少轮
  3. 如果元素A能移除元素B，元素B能移除元素C，那么元素C被移除的轮数至少是元素B被移除轮数+1

算法思路

使用单调栈来解决：

  • 维护一个递减的单调栈，存储元素的下标
  • 对于当前元素 nums[i]，如果它大于等于栈顶元素对应的值，说明当前元素可以"保护"或"移除"栈顶元素
  • 当我们弹出栈顶元素时，被弹出元素的移除轮数应该是它原本的轮数+1，但同时也要考虑当前元素本身可能需要的轮数

动态规划状态转移

  • dp[i] 表示第i个元素被移除需要的轮数
  • 当元素j被元素i移除时，dp[i] = max(dp[i], dp[j] + 1)
  • 最终答案是所有 dp[i] 的最大值

代码实现

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);  // dp[i]表示第i个元素被移除需要的轮数
        stack<int> st;  // 单调递减栈，存储下标
        int maxSteps = 0;
        
        for (int i = 0; i < n; i++) {
            // 当前元素可以移除栈中比它小的元素
            while (!st.empty() && nums[st.top()] <= nums[i]) {
                dp[i] = max(dp[i], dp[st.top()] + 1);
                st.pop();
            }
            st.push(i);
            maxSteps = max(maxSteps, dp[i]);
        }
        
        return maxSteps;
    }
};

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n  # dp[i]表示第i个元素被移除需要的轮数
        stack = []  # 单调递减栈，存储下标
        max_steps = 0
        
        for i in range(n):
            # 当前元素可以移除栈中比它小的元素
            while stack and nums[stack[-1]] <= nums[i]:
                dp[i] = max(dp[i], dp[stack[-1]] + 1)
                stack.pop()
            stack.append(i)
            max_steps = max(max_steps, dp[i])
        
        return max_steps

public class Solution {
    public int TotalSteps(int[] nums) {
        int n = nums.Length;
        int[] dp = new int[n];  // dp[i]表示第i个元素被移除需要的轮数
        Stack<int> stack = new Stack<int>();  // 单调递减栈，存储下标
        int maxSteps = 0;
        
        for (int i = 0; i < n; i++) {
            // 当前元素可以移除栈中比它小的元素
            while (stack.Count > 0 && nums[stack.Peek()] <= nums[i]) {
                dp[i] = Math.Max(dp[i], dp[stack.Pop()] + 1);
            }
            stack.Push(i);
            maxSteps = Math.Max(maxSteps, dp[i]);
        }
        
        return maxSteps;
    }
}

var totalSteps = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(0);  // dp[i]表示第i个元素被移除需要的轮数
    const stack = [];  // 单调递减栈，存储下标
    let maxSteps = 0;
    
    for (let i = 0; i < n; i++) {
        // 当前元素可以移除栈中比它小的元素
        while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[i]) {
            dp[i] = Math.max(dp[i], dp[stack.pop()] + 1);
        }
        stack.push(i);
        maxSteps = Math.max(maxSteps, dp[i]);
    }
    
    return maxSteps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 每个元素最多入栈和出栈一次
空间复杂度O(n) - 需要dp数组和单调栈存储

相关题目