समस्या
एक मूव में आप ऐरे के किसी एक मान को 1 से बढ़ा सकते हैं। ऐरे को गैर-घटती (nondecreasing) बनाएं: प्रत्येक मान अपने ठीक पिछले मान के बराबर या उससे अधिक होना चाहिए। आप किसी मान को घटा या ऐरे को रीऑर्डर नहीं कर सकते।
increasing_array(numbers) को इम्प्लीमेंट करें।
इनपुट
numbers: मान अपने मूल क्रम में।
आउटपुट
यूनिट इन्क्रीमेंट्स की न्यूनतम कुल संख्या लौटाएं।
सीमाएँ
1 ≤ लंबाई ≤ 200,000। प्रत्येक मान 1 और 1,000,000,000 के बीच है। परिणाम के लिए साइन किए गए 64-बिट का उपयोग करें।
उदाहरण
इनपुट:
numbers = [4, 1, 3]
अपेक्षित आउटपुट:
expected = 4इनपुट:
std::vector<long long> numbers = {4, 1, 3};
अपेक्षित आउटपुट:
long long expected = 4;इनपुट:
long[] numbers = new long[] {4, 1, 3};
अपेक्षित आउटपुट:
long expected = 4;व्याख्या
1 को 4 तक बढ़ाने के लिए तीन मूव्स और 3 को 4 तक बढ़ाने के लिए एक मूव लगती है। परिणाम [4, 4, 4] के लिए कुल चार मूव्स लगती हैं।
इनपुट:
numbers = [1, 2, 2, 5]
अपेक्षित आउटपुट:
expected = 0इनपुट:
std::vector<long long> numbers = {1, 2, 2, 5};
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long[] numbers = new long[] {1, 2, 2, 5};
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
हर मान पहले वाले के बराबर या उससे अधिक है; बराबर पड़ोसी मान भी मान्य हैं।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Left to right scan करो, क्योंकि हर value सिर्फ previous पर depend करती है.
संकेत 2
जब कोई value बहुत छोटी हो, उसे बस इतना बढ़ाओ कि running minimum allowed value match हो जाए.
संकेत 3
Total increments को carefully track करो, क्योंकि earlier increases बाद की comparisons को affect करते हैं.
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।