我正在研究一个优化问题，即找到一个最大化某个目标函数的区域，我使用一组像素坐标来跟踪该区域，并且每一步我都会在边界处添加或删除一个像素，以查看目标函数是否增加。我希望该区域是连通的，是否有任何数据结构可以快速决定删除一个像素是否会使该区域断开连接？这里我们假设一个像素与其四个邻居相连。
还有一个类似的问题：如果我希望该区域始终是单连通的，该怎么办？单连通的意思是没有洞，而添加一个像素可能会产生一个洞。
该问题基于 leetcode 竞赛问题 ( https://doocs.github.io/leetcode/en/lc/3281/ )。可以将其简化为以下问题：设s为已排序数组，d为正整数，最小化 ( s [i]- s [j]+ d )/(ij)。其中 i>j。
大多数答案都是基于二分搜索来限制最优解，其时间复杂度取决于 max( s )-min( s )。那么，是否有可能构建一个相对于s大小线性/次二次的算法？