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

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] = 3

A[1] = 4

A[2] = 4

A[3] = 6

A[4] = 1

A[5] = 4

A[6] = 4

the 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), or

a vector of integers (in C++), or

a record Results (in Pascal), or

an 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] = 4

the 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对其进行更新，仅在乎最新。