Back to Leetcode

Readme

Thinking/2860.Happy-Students/Readme.md

latest763 B
Original Source

2860.Happy-Students

我们发现,将nums按照从小到大排序后,如果第i个同学选中并且happy,那么比他小的同学必须选中才能happy。如果第j个同学没选中并且happy,那么比他大的同学也一定要不被选中才能happy。

因为所有的同学都happy,这就告诉我们,所有选中的同学必然是相邻的,所有没有选中的同学必然是相邻的。所以我们需要找到这个分界点。只需要遍历所有的间隔位置,判断如果左边选中、右边不选中,是否能够满足让他们两个happy(其他人自然自动满足)。

注意这样的分界点没有连续性,它可能离散地出现在任何位置。

此外注意全部选中和全部不选两种特殊情况。