Hướng giải quyết bài 135.Candy trên leetcode

https://leetcode.com/problems/candy/description/


Đề bài:
Có n em đứng thành một hàng. Mỗi em được gán một giá trị xếp hạng cho trong mảng số nguyên chứa xếp hạng.
Bạn đang tặng kẹo cho các em với điều kiện sau:
-Mỗi đứa em phải có ít nhất một viên kẹo.
-Những em có điểm xếp hạng cao hơn sẽ nhận được nhiều kẹo hơn những đứa trẻ cạnh bên.
Trả lại số lượng kẹo tối thiểu bạn cần để phân phát kẹo cho các em.

Cách giải quyết:
-Chúng ta có thể tư duy từ đề bài rằng
từ nếu thứ hạng tại i bất kì thấp hơn 2 thứ hạng cạnh bên ( vị trí i-1 và i+1) thì không quan trọng khoảng cách giữa các thứ hạng là bao nhiêu, chúng ta hoàn toàn có thể phát 1 viên kẹo cho đứa trẻ đỏ
-> chúng ta xác định các điểm "đáy" ( có thứ hạng 2 thứ hạng của 2 bạn cạnh bên ) là 1  (giả sử là i) 
=> để tối ưu thì i-1 và i+1 sẽ được phát 2 viên kẹo và cứ như vậy ( giống như các cơn sóng )
 TUY NHIÊN: sẽ có trường hợp các cơn sóng nói trên giao nhau, lúc đó thì vì luật thứ 2 "Những em có điểm xếp hạng cao hơn sẽ nhận được nhiều kẹo hơn những em cạnh bên."
chúng ta sẽ lấy giá trị cao hơn +1.

Thông qua bài này chúng ta có thể:
-Quen thuộc hơn với các vetor
-Tăng khả năng tư duy cũng như giải bài