समस्या
One move increases one array value by 1. Make the array nondecreasing: each value must be greater than or equal to the one immediately before it. You may not decrease values or reorder them.
Implement increasing_array(numbers).
Input
numbers: The values in their original order.
Output
Return the minimum total number of unit increments.
सीमाएँ
1 ≤ length ≤ 200,000. Each value is between 1 and 1,000,000,000. Use a signed 64-bit result.
उदाहरण
इनपुट:
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;व्याख्या
Raise 1 to 4 using three moves and 3 to 4 using one move. The result [4, 4, 4] uses four moves.
इनपुट:
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;व्याख्या
Every value is already at least the preceding value; equal neighbors are allowed.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Scan from left to right, because each value only depends on the previous one.
संकेत 2
Whenever a value is too small, raise it just enough to match the running minimum allowed value.
संकेत 3
Track the total increments carefully, since earlier increases affect later comparisons.
अपेक्षित जटिलता
O(n) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।