@ninijia 在 Leetcode每日一题练习 ------ 2779. 数组的最大美丽值 中发帖
从Leetcode 每日一题练习继续讨论:
2779. 数组的最大美丽值
2779. Maximum Beauty of an Array After Applying Operation
题解
首先注意本题要找的是最长的子序列而不是子数组,因此不需要数字之间相邻,数字的先后顺序在本题中也不重要。考虑题目中允许的操作为将任意一个数字加上k或者减去k,且该操作只能执行一次。则设当前的数字为i,则在i-k和i+k范围内的全部数字均可通过题目所述操作变为相同数字。这个范围的大小是固定的2k,因此可以使用滑动窗口不断确定在这个范围内的所有数字的个数。
使用滑动窗口要有一个窗口的增长和收缩条件,我们知道要将窗口的范围始终限制在2k,则可先移动窗口左端的数字,使其变大,再根据左侧数字确定右侧的数字范围,移动窗口右侧的指针。这要求数组必须是有序的,有序情况下窗口左右才可以随着指针的移动数值自然变...