135. Candy

Problem

Bài toán yêu cầu phân phát kẹo cho các trẻ em xếp thành hàng dựa trên mảng ratings sao cho:

Mỗi trẻ nhận ít nhất 1 viên kẹo

Trẻ nào có rating cao hơn hàng xóm (bên trái hoặc phải) thì phải nhận nhiều kẹo hơn hàng xóm đó

Tổng số kẹo phát ra là ít nhất

Approach

Giải pháp phổ biến là sử dụng hai lượt duyệt (greedy 2 chiều)

Duyệt từ trái sang phải

Nếu rating của trẻ hiện tại lớn hơn trẻ bên trái, thì số kẹo của trẻ hiện tại = số kẹo của trẻ bên trái + 1

Duyệt từ phải sang trái

Nếu rating của trẻ hiện tại lớn hơn trẻ bên phải, thì số kẹo của trẻ hiện tại = max(số kẹo hiện tại, số kẹo của trẻ bên phải + 1)

Cuối cùng, tổng số kẹo là tổng lớn nhất của hai lượt duyệt ở mỗi vị trí

Time and space complexity

TC: O(n)

SC: O(n)

Solution

typescripttypescript

1function candy(ratings: number[]): number {
2    const n = ratings.length;
3    const left = Array(n).fill(1);
4    const right = Array(n).fill(1);
5    for (let i = 1; i < n; i++) {
6        if (ratings[i] > ratings[i - 1]) {
7            left[i] = left[i - 1] + 1
8        }
9    }
10
11    for (let i = n - 2; i >= 0; i--) {
12        if (ratings[i] > ratings[i + 1]) {
13            right[i] = right[i + 1] + 1
14        }
15    }
16
17    let total = 0;
18    for (let i = 0; i < n; i++) {
19        total += Math.max(left[i], right[i])
20    }
21
22    return total
23};

💡

Giải thích ngắn gọn

Mỗi trẻ em nhận ít nhất 1 kẹo

Duyệt hai chiều để đảm bảo mọi trường hợp so sánh với hàng xóm đều được xử lý

Lấy giá trị lớn nhất giữa hai lượt duyệt cho mỗi trẻ để đảm bảo điều kiện bài toán

💡

Tại sao lại có điều kiện total += Math.max(left[i], right[i]);

Điều kiện total += Math.max(left[i], right[i]); xuất hiện trong thuật toán là để đảm bảo rằng mỗi trẻ em đều thỏa mãn cả hai điều kiện so sánh với hàng xóm bên trái và bên phải

Cụ thể

Sau lượt duyệt từ trái sang phải, mảng left[i] đảm bảo rằng nếu rating của trẻ em hiện tại lớn hơn trẻ em bên trái thì số kẹo của nó cũng nhiều hơn

Sau lượt duyệt từ phải sang trái, mảng right[i] đảm bảo rằng nếu rating của trẻ hiện tại lớn hơn trẻ bên phải thì số kẹo của nó cũng nhiều hơn.

Tuy nhiên, có thể tại một vị trí nào đó, số kẹo cần thiết để thỏa mãn điều kiện trái khác với phải. Để đảm bảo cả hai điều kiện đúng, ta phải lấy số lớn nhất giữa hai giá trị này cho mỗi trẻ em tức là Math.max(left[i], right[i])

Nếu chỉ lấy giá trị nhỏ hơn, sẽ có trường hợp vi phạm một trong hai điều kiện so sánh với hàng xóm, việc lấy giá trị lớn nhất đảm bảo mọi quy tắc của đề bài đều được đáp ứng cho từng trẻ em, và tổng số kẹo là nhỏ nhất có thể mà không vi phạm luật phân phát kẹo nào

Loading content...

1function candy(ratings: number[]): number { 2 const n = ratings.length; 3 const left = Array(n).fill(1); 4 const right = Array(n).fill(1); 5 for (let i = 1; i < n; i++) { 6 if (ratings[i] > ratings[i - 1]) { 7 left[i] = left[i - 1] + 1 8 } 9 } 10 11 for (let i = n - 2; i >= 0; i--) { 12 if (ratings[i] > ratings[i + 1]) { 13 right[i] = right[i + 1] + 1 14 } 15 } 16 17 let total = 0; 18 for (let i = 0; i < n; i++) { 19 total += Math.max(left[i], right[i]) 20 } 21 22 return total 23};

Related Posts

Related Posts

135. Candy

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists