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

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).

我有一个解决方案，

public static int[] solution(int N, int[] A) {

        int[] counters = new int[N];

        int currMax = 0;
        int currMin = 0;

        for (int i = 0; i < A.length; i++) {

            if (A[i] <= N) {

                counters[A[i] - 1] = Math.max(currMin, counters[A[i] - 1]);
                counters[A[i] - 1]++;

                currMax = Math.max(currMax, counters[A[i] - 1]);
            } else if (A[i] == N + 1) {
                currMin = currMax;
            }
        }

        for (int i = 0; i < counters.length; i++) {
            counters[i] = Math.max(counters[i], currMin);
        }

        return counters;
    }

他们似乎使用 2 个存储来保存和更新最小/最大值并在算法中使用它们。显然，有一种更直接的方法可以解决问题即。按照建议将值增加 1 或将所有值设置为最大值，我可以做到。缺点是会降低性能并增加时间复杂度。

但是，我想了解这里发生了什么。我花了很多时间调试示例数组，但算法仍然有点困惑。

有谁看得懂，能简单解释一下吗？

Answer 1

这很简单，他们做惰性更新。您始终跟踪具有最高值 (currMax) 的计数器的值是多少。然后，当您收到将所有计数器增加到该 maxValue 的命令时，因为这太昂贵了，您只需保存上次必须将所有计数器增加到 maxValue 时的值，该值是 currMin。

那么，您何时将计数器值更新为该值？你懒惰地做，当你得到一个命令来更新那个计数器(增加它)时，你就更新它。所以当你需要增加一个计数器时，你将计数器更新为它的旧值和 currMin 之间的最大值。如果这是自 N + 1 命令以来此计数器的第一次更新，则它应该具有的正确值实际上是 currMin，并且将高于(或等于)其旧值。一个你更新它，你给它加 1。如果现在发生另一个增加，currMin 实际上并不重要，因为最大值将采用其旧值，直到另一个 N + 1 命令发生。

第二个 for 是考虑在最后一个 N + 1 命令后没有得到增加命令的计数器。

请注意，在计数器的 2 次递增操作之间可以有任意数量的 N + 1 命令。它仍然遵循它应该具有的值是最后一个 N + 1 命令时的 maxValue，我们之前没有用前一个 N + 1 的另一个 maxValue 更新它并不重要，我们只关心最新的。