Đề bài
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.
Ràng buộc
1 ≤ length ≤ 200,000. Each value is between 1 and 1,000,000,000. Use a signed 64-bit result.
Ví dụ
Đầu vào:
numbers = [4, 1, 3]
Kết quả mong đợi:
expected = 4Đầu vào:
std::vector<long long> numbers = {4, 1, 3};
Kết quả mong đợi:
long long expected = 4;Đầu vào:
long[] numbers = new long[] {4, 1, 3};
Kết quả mong đợi:
long expected = 4;Giải thích
Raise 1 to 4 using three moves and 3 to 4 using one move. The result [4, 4, 4] uses four moves.
Đầu vào:
numbers = [1, 2, 2, 5]
Kết quả mong đợi:
expected = 0Đầu vào:
std::vector<long long> numbers = {1, 2, 2, 5};
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long[] numbers = new long[] {1, 2, 2, 5};
Kết quả mong đợi:
long expected = 0;Giải thích
Every value is already at least the preceding value; equal neighbors are allowed.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Scan from left to right, because each value only depends on the previous one.
Gợi ý 2
Whenever a value is too small, raise it just enough to match the running minimum allowed value.
Gợi ý 3
Track the total increments carefully, since earlier increases affect later comparisons.
Độ phức tạp mong đợi
O(n) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.