Đề bài
Mỗi lần di chuyển, bạn có thể tăng một giá trị trong mảng lên 1. Hãy biến mảng thành không giảm: mỗi giá trị phải lớn hơn hoặc bằng giá trị ngay trước nó. Bạn không được giảm giá trị hoặc thay đổi thứ tự các phần tử.
Cài đặt hàm increasing_array(numbers).
Đầu vào
numbers: Các giá trị theo thứ tự ban đầu.
Đầu ra
Trả về tổng số lần tăng đơn vị tối thiểu.
Ràng buộc
1 ≤ độ dài ≤ 200.000. Mỗi giá trị nằm trong khoảng từ 1 đến 1.000.000.000. Sử dụng kết quả kiểu số nguyên có dấu 64-bit.
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
Tăng 1 lên 4 bằng ba lần và tăng 3 lên 4 bằng một lần. Kết quả [4, 4, 4] sử dụng bốn lần tăng.
Đầ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
Mỗi giá trị đã không nhỏ hơn giá trị liền trước; các giá trị liền kề bằng nhau là hợp lệ.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Duyệt từ trái sang phải, vì mỗi giá trị chỉ phụ thuộc vào giá trị trước đó.
Gợi ý 2
Khi một giá trị quá nhỏ, tăng nó vừa đủ để khớp với mức tối thiểu đang được phép.
Gợi ý 3
Theo dõi tổng số lần tăng cẩn thận, vì các lần tăng trước ảnh hưởng đến so sánh sau.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
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.