应用所有交替操作后计算计数器的值

Question

我正在尝试Codility使用给定的解决方案来解决的问题。该问题在下面提供：You are given N counters, initially set to 0, and you have two possible operations on them:increase(X) − counter X is increased by 1,max counter − all counters are set to the maximum value of any counter.A non-empty array A of M integers is given. This array represents consecutive operations:if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),if A[K] = N + 1 then operation K is max counter.For example, given integer N = 5 and array A such that:A[0] = 3A[1] = 4A[2] = 4A[3] = 6A[4] = 1A[5] = 4A[6] = 4the values of the counters after each consecutive operation will be:(0, 0, 1, 0, 0)(0, 0, 1, 1, 0)(0, 0, 1, 2, 0)(2, 2, 2, 2, 2)(3, 2, 2, 2, 2)(3, 2, 2, 3, 2)(3, 2, 2, 4, 2)The goal is to calculate the value of every counter after all operations.Write a function:class Solution { public int[] solution(int N, int[] A); }that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.The sequence should be returned as:a structure Results (in C), ora vector of integers (in C++), ora record Results (in Pascal), oran array of integers (in any other programming language).For example, given:    A[0] = 3    A[1] = 4    A[2] = 4    A[3] = 6    A[4] = 1    A[5] = 4    A[6] = 4the function should return [3, 2, 2, 4, 2], as explained above.Assume that:N and M are integers within the range [1..100,000];each element of array A is an integer within the range [1..N + 1].Complexity:    expected worst-case time complexity is O(N+M);    expected worst-case space complexity is O(N) (not counting the storage required for input arguments).看来他们使用2个存储来保存和更新最小值/最大值，并在算法中使用它们。显然，有一种更直接的方法可以解决该问题。将值增加1或将所有值都设置为建议的最大值，我可以做到这一点。缺点将是降低性能并增加时间复杂度。但是，我想了解这里的情况。我花了很多时间在示例数组上进行调试，但是该算法仍然没有什么令人困惑的地方。任何人都可以理解并可以向我简要说明吗？

Answer 1

这很简单，他们会延迟更新。您始终跟踪具有最高值（currMax）的计数器的值。然后，当您获得将所有计数器增加到该maxValue的命令时，这太昂贵了，您只是保存了上一次必须将所有计数器增加到maxValue时的那个值是currMin。

那么，何时将计数器值更新为该值？您懒惰地执行它，只是在收到命令更新该计数器（增加它）时才对其进行更新。因此，当您需要增加计数器时，可以将计数器更新为其旧值和currMin之间的最大值。如果这是自N + 1命令以来对该计数器的第一次更新，则它应具有的正确值实际上是currMin，并且它将大于（或等于）其旧值。一个您更新它，您添加1。如果现在又发生了一次增量，则currMin实际上并不重要，因为max将采用其旧值，直到发生另一个N + 1命令为止。

第二个原因是要说明在最后一个N + 1命令之后没有获得增加命令的计数器。

请注意，在一个计数器上进行2次增值操作之间可以有任意数量的N + 1命令。仍然得出结论，它应该具有的值是最后一个N + 1命令时的maxValue，这并不重要，我们之前没有使用先前N + 1中的另一个maxValue对其进行更新，仅在乎最新。