3048. 标记索引的最早秒数 I

Medium

题目描述

给你两个长度分别为 n 和 m 的 1 索引整数数组 nums 和 changeIndices。

一开始，nums 中所有索引都是未标记的。你的任务是标记 nums 中的所有索引。

在每一秒 s（从 1 到 m 包含边界），你可以执行以下操作之一：

选择范围 [1, n] 内的一个索引 i 并将 nums[i] 减少 1。
如果 nums[changeIndices[s]] 等于 0，标记索引 changeIndices[s]。
什么也不做。

返回一个整数，表示通过最优选择操作能够标记 nums 中所有索引的范围 [1, m] 内的最早秒数，如果不可能则返回 -1。

示例 1：

输入：nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
输出：8

示例 2：

输入：nums = [1,3], changeIndices = [1,1,1,2,1,1,1]
输出：6

示例 3：

输入：nums = [0,1], changeIndices = [2,2,2]
输出：-1

提示：

1 <= n == nums.length <= 2000
0 <= nums[i] <= 10^9
1 <= m == changeIndices.length <= 2000
1 <= changeIndices[i] <= n

解题思路

这是一道典型的二分搜索 + 贪心验证的题目。

核心思路： 要标记所有索引，我们必须先通过减操作将每个索引的值减到0，然后在对应的changeIndices时机进行标记。关键观察是：如果我们能在时间T内完成所有标记，那么也能在更长时间内完成，这具有单调性，适合二分搜索。

算法步骤：

二分搜索答案，范围是 [1, m]
对于每个候选时间T，验证是否可行：
- 找到每个索引在时间T内的最后一次出现位置
- 如果某个索引在时间T内没有出现，直接返回false
- 从后往前贪心处理：优先处理后面的标记时机
- 对于每个标记时机，检查是否有足够的时间进行减操作

验证逻辑： 设当前处理到秒数i，需要标记索引idx，其值为nums[idx]。我们需要确保：

在标记前有足够时间将nums[idx]减到0
计算公式：可用时间 >= nums[idx]
可用时间 = i - 已占用的标记次数 - 已消耗的减操作次数

这种贪心策略是最优的，因为我们总是在最晚可能的时机进行标记，从而最大化可用于减操作的时间。

代码实现

class Solution {
public:
    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
        int n = nums.size();
        int m = changeIndices.size();
        
        auto check = [&](int t) -> bool {
            vector<int> lastOccur(n + 1, -1);
            for (int i = 0; i < t; i++) {
                lastOccur[changeIndices[i]] = i;
            }
            
            for (int i = 1; i <= n; i++) {
                if (lastOccur[i] == -1) return false;
            }
            
            long long sumDecrements = 0;
            int markedCount = 0;
            
            for (int i = t - 1; i >= 0; i--) {
                int idx = changeIndices[i];
                if (lastOccur[idx] == i) {
                    if (i - markedCount - sumDecrements < nums[idx - 1]) {
                        return false;
                    }
                    sumDecrements += nums[idx - 1];
                    markedCount++;
                }
            }
            return true;
        };
        
        int left = 1, right = m, ans = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};

class Solution:
    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
        n = len(nums)
        m = len(changeIndices)
        
        def check(t):
            last_occur = [-1] * (n + 1)
            for i in range(t):
                last_occur[changeIndices[i]] = i
            
            for i in range(1, n + 1):
                if last_occur[i] == -1:
                    return False
            
            sum_decrements = 0
            marked_count = 0
            
            for i in range(t - 1, -1, -1):
                idx = changeIndices[i]
                if last_occur[idx] == i:
                    if i - marked_count - sum_decrements < nums[idx - 1]:
                        return False
                    sum_decrements += nums[idx - 1]
                    marked_count += 1
            
            return True
        
        left, right = 1, m
        ans = -1
        
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return ans

public class Solution {
    public int EarliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
        int n = nums.Length;
        int m = changeIndices.Length;
        
        bool Check(int t) {
            int[] lastOccur = new int[n + 1];
            Array.Fill(lastOccur, -1);
            
            for (int i = 0; i < t; i++) {
                lastOccur[changeIndices[i]] = i;
            }
            
            for (int i = 1; i <= n; i++) {
                if (lastOccur[i] == -1) return false;
            }
            
            long sumDecrements = 0;
            int markedCount = 0;
            
            for (int i = t - 1; i >= 0; i--) {
                int idx = changeIndices[i];
                if (lastOccur[idx] == i) {
                    if (i - markedCount - sumDecrements < nums[idx - 1]) {
                        return false;
                    }
                    sumDecrements += nums[idx - 1];
                    markedCount++;
                }
            }
            return true;
        }
        
        int left = 1, right = m, ans = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (Check(mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

var earliestSecondToMarkIndices = function(nums, changeIndices) {
    const n = nums.length;
    const m = changeIndices.length;
    
    // Check if all indices can be marked
    const canMark = new Set();
    for (let i = 0; i < m; i++) {
        canMark.add(changeIndices[i] - 1);
    }
    for (let i = 0; i < n; i++) {
        if (!canMark.has(i)) return -1;
    }
    
    function canMarkAll(maxTime) {
        // Find last occurrence of each index within maxTime
        const lastOccur = new Array(n).fill(-1);
        for (let i = 0; i < maxTime; i++) {
            lastOccur[changeIndices[i] - 1] = i;
        }
        
        // Check if all indices have at least one occurrence
        for (let i = 0; i < n; i++) {
            if (lastOccur[i] === -1) return false;
        }
        
        // Greedy: mark indices at their last possible time
        const marked = new Array(n).fill(false);
        const markTime = new Array(maxTime).fill(-1);
        
        for (let i = 0; i < n; i++) {
            markTime[lastOccur[i]] = i;
        }
        
        // Simulate the process
        const current = [...nums];
        let decrements = 0;
        
        for (let t = 0; t < maxTime; t++) {
            if (markTime[t] !== -1) {
                // Must mark this index
                const idx = markTime[t];
                if (current[idx] > 0) return false;
                marked[idx] = true;
            } else {
                // Can decrement
                decrements++;
            }
        }
        
        // Check if we have enough decrements
        let needed = 0;
        for (let i = 0; i < n; i++) {
            needed += nums[i];
        }
        
        return decrements >= needed;
    }
    
    let left = 1, right = m;
    let result = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canMarkAll(mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	大小
时间复杂度	O(m log m * n)
空间复杂度	O(n)

说明：

时间复杂度：二分搜索需要 O(log m) 次，每次验证需要 O(m + n) 时间
空间复杂度：主要用于存储每个索引的最后出现位置

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析