Tất cả thử thách
Dễ 1 đã giải Tỷ lệ chấp nhận 9.1%

Biến Mảng Thành Không Giảm

Tìm số lần tăng tối thiểu để mỗi giá trị không nhỏ hơn giá trị liền trước.

Bạn sẽ học được gì

  • Sửa mỗi giá trị so với giá trị trước
  • Đếm tổng số bước cần thiết
  • Hiểu vì sao lựa chọn tham lam là tối ưu

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 HJhettory Jurash Python 803 ms - 4/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.