Leetcode 3048. Earliest Second to Mark Indices I

• Leetcode 3048. Earliest Second to Mark Indices I
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3048. Earliest Second to Mark Indices I

1. 解题思路

这一题的话基础的思路就是二分法查找最小的可以将所有的数字都mark上的最小位置。

因此，这里的问题就会变成如何快速地判断对于一个给定的位置，能否在这个操作序列下将所有的数字全部mark上。

而考虑的可能的操作，显然有：

• 要将一个数mark上，必须在某次操作时其给出的mark indice正好为这个位置，且之前已经将其减为0了。

因此，我们就要确保：

1. 在对应的操作序列下所有的位置至少都出现过一次；
2. 在最后一次出现某一位置的操作前，我们可以将对应位置上的值变为0；

因此，我们只需要对每一个长度的操作序列，判断其各个位置的操作是否齐全以及其最后一次操作的位置，然后分配一下decrease的顺序是否可以满足即可。

2. 代码实现

给出python代码实现如下：

class Solution:def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:n, m = len(nums), len(changeIndices)changeIndices = [x-1 for x in changeIndices]idxs = defaultdict(list)for i, x in enumerate(changeIndices):idxs[x].append(i)def get_last_index(n):last_index = {}for k, v in idxs.items():idx = bisect.bisect_right(v, n)-1if idx == -1:breaklast_index[v[idx]] = nums[k]return last_indexdef is_possible(k):last_index = get_last_index(k)if len(last_index) < n:return Falsecnt = 0for i in range(k+1):if i not in last_index:cnt += 1elif cnt < last_index[i]:return Falseelse:cnt -= last_index[i]return Trueif not is_possible(m-1):return -1i, j = sum(nums) + len(nums)-2, m-1while j-i>1:k = (i+j)//2if is_possible(k):j = kelse:i = kreturn j+1

提交代码评测得到：耗时135ms，占用内存17.5MB。