Respectable
MaxCounters
すべての交互の操作を適用した後、カウンターの値を計算します。カウンターを1つ増やします。 すべてのカウンターの値を現在の最大値に設定します。
タスク説明
最初は0に設定されたN個のカウンターが与えられ、それらに対して2つの可能な操作があります。
増加（X）-カウンターXが1増加します。
max counter-すべてのカウンターは、任意のカウンターの最大値に設定されます。
M個の整数の空でない配列Aが与えられます。この配列は、連続する操作を表します。
- A [K] = Xで、1≤X≤Nの場合、操作Kはincrease（X）、
- A [K] = N + 1の場合、操作Kは最大カウンターです。
たとえば、整数N = 5で、配列Aが次のようになっているとします。
A [0] = 3
A [1] = 4
A [2] = 4
A [3] = 6
A [4] = 1
A [5] = 4
A [6] = 4
連続する各操作後のカウンターの値は次のようになります。
（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）
目標は、すべての操作の後にすべてのカウンターの値を計算することです。
関数を書く：
class solution {public int [] solution（int N、int [] A）; }
これは、整数NとM個の整数で構成される空でない配列Aが与えられると、カウンターの値を表す整数のシーケンスを返します。
結果の配列は、整数の配列として返される必要があります。
たとえば、次のようになります。
A [0] = 3
A [1] = 4
A [2] = 4
A [3] = 6
A [4] = 1
A [5] = 4
A [6] = 4
上で説明したように、関数は[3、2、2、4、2]を返す必要があります。
次の仮定のための効率的なアルゴリズムを記述します。
- NとMは、[1..100,000]の範囲内の整数です。
- 配列Aの各要素は、[1..N +1]の範囲内の整数です。
解く
著者注
この問題の鍵は、MaxCounterが発生したときに、配列のすべてのメンバーに現在の最大要素値を割り当てる必要があることです。配列メンバーが多数ある場合、各メンバーに値を割り当てたり、頻繁に値を割り当てたりすると、かなりの計算が発生します。
これはインターネットの同時実行性が高い場面で**「ストーム」**と呼ばれます、たとえネットワークストーム、キャッシュストーム、雪崩など。ストームまたは頻繁なストームが発生した場合、それはシステムに壊滅的です。
「ストーム」には多くの理由があり、対応する対策も異なります。今回問題の鍵は、「全要素の割り当て」の問題にどのように対処するか、そして頻繁な「全要素の割り当て」の場合でも高いパフォーマンスを維持できるかどうかを検討することにあります。
作者 Roc Yang 备注：
这个问题的关键在于：发生MaxCounter时，数组全员要赋为当前最大的元素值，当存在大量数组成员时，对每个成员赋值，甚至频繁赋值，所产生的计算量的相当可观的。
这在互联网高并发场景下，通常被称为**“风暴”**，比如网络风暴，缓存风暴、雪崩等。若发生风暴或风暴频繁发生，对系统将是灾难性的。
“风暴”产生的原因有很多，相应的对策也不同。本题的解决关键在于如何处理“全员赋值”的问题，并要考虑到频繁发生“全员赋值”的情况下，是否仍然能够保持高性能。
Program
著者ロックヤン注：
ここで使用されるソリューション：
この問題では、MaxCounterが発生したときに、すべての配列要素を現在の最大要素値に割り当てる必要があります（したがって、ストームが発生する可能性があります）。
MaxCounterが発生したときに、現在の最大要素値を一時的に書き留め、次に要素が+1操作を実行するときに、要素のMaxCounter操作を追加（つまり、最大値と+1を割り当てる）した場合、ストームは発生しません。
注：+1操作はすべての要素で発生するわけではないため、すべての要素がMaxCounter操作で埋められているかどうかを確認する必要があります。
（この方法はインターネットアプリケーションでよく使用されます。たとえば、SNSのシナリオでは、大きなVが記事を投稿します。大きなVの記事を購読したユーザーがすぐに記事のコンテンツをプッシュすると、ストームが発生する可能性があります。
クライアントがログインしたときにのみ、クライアントがサブスクライブした記事をプルすると、嵐は効果的に回避されます。
もちろん、実際のSNSシナリオでは、サブスクライブしたユーザーに通知を送信するなど、考慮する必要のある他の複雑なサービスがあるため、ここでは説明しません。興味のある友達、メッセージを残して一緒に議論することを歓迎します。 ）
作者 Roc Yang 备注：
这里用到的解决方法：
题目要求当MaxCounter发生时，应把所有数组元素 赋值为当前最大元素值（因而可能产生风暴）。
若，当MaxCounter发生时，把当前最大元素值暂且记下，当下次某元素做+1操作时再补上该元素的MaxCounter操作（即 赋值为最大值，并+1），那么风暴就不会出现了。
注意：因未必每个元素都会发生+1操作，所有最终要检查是否所有元素都已经补上MaxCounter操作。
（该方法在互联网应用中经常使用，比如SNS的场景中，大V发文章，若立即向订阅了大V文章的用户，每人都推送文章内容，很可能产生风暴。
若仅当客户端登录时，由客户端拉取自己订阅的文章，那么将有效的避免风暴的发生。
当然，真正的SNS场景中，存在其他的复杂业务，比如要向订阅的user发送通知等场景需要考虑，不在这里展开讨论。有兴趣的朋友，欢迎留言一起探讨。）
public int[] solution(int N, int[] A) {
int[] B = new int[N];
int currentMaximumValue = 0;
int minValue = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] == N + 1) {
if (minValue < currentMaximumValue) {
minValue = currentMaximumValue;
}
} else {
if (B[A[i] - 1] < minValue) {
B[A[i] - 1] = minValue;
}
B[A[i] - 1] += 1;
if (B[A[i] - 1] > currentMaximumValue) currentMaximumValue = B[A[i] - 1];
}
}
for (int j = 0; j < B.length; j++) {
B[j] = B[j] < minValue ? minValue : B[j];
}
return B;
}
jUnit
Report
Candidate Report: training9KQG2K-34P
Detected time complexity:
O(N + M)