我试图用给定的解决方案从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 或按照建议将所有值设置为 max，我可以做到这一点。缺点是性能降低，时间复杂度增加。
但是，我想了解这里发生了什么。我花时间调试示例数组，但算法仍然有点混乱。
有人明白并可以向我简要解释吗？
这很简单，他们做懒惰的更新。您始终跟踪具有最高值 (currMax( 的计数器的值。然后，当您收到将所有计数器增加到该 maxValue 的命令时，因为这太昂贵了，您只需保存上次必须将所有计数器增加到 maxValue 时，该值为 currMin。
那么，何时将计数器值更新为该值？你懒惰地做，你只是在收到更新该计数器的命令时更新它(增加它(。因此，当您需要增加计数器时，您可以将计数器更新到其旧值和 currMin之间的最大值。如果这是自 N + 1 命令以来此计数器的第一次更新，则它应该具有的正确值实际上是 currMin，这将高于(或等于(其旧值。一个你更新了它，你给它加了 1。如果现在发生另一次增加，currMin 实际上并不重要，因为最大值将采用其旧值，直到另一个 N + 1 命令发生。
第二个 for 是考虑在最后一个 N + 1 命令之后未获得增加命令的计数器。
请注意，计数器上的 2 个增加操作之间可以有任意数量的 N + 1 个命令。它应该具有的值仍然是最后一个 N + 1 命令时的 maxValue，我们之前没有使用前一个 N + 1 中的另一个 maxValue 更新它并不重要，我们只关心最新的。