题目大意：
查找大小为 M 的最新分组
给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。
给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。
返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。
示例 1：
输入：arr = [3,5,1,2,4], m = 1 输出：4 解释： 步骤 1："00100"，由 1 构成的组：["1"] 步骤 2："00101"，由 1 构成的组：["1", "1"] 步骤 3："10101"，由 1 构成的组：["1", "1", "1"] 步骤 4："11101"，由 1 构成的组：["111", "1"] 步骤 5："11111"，由 1 构成的组：["11111"] 存在长度为 1 的一组 1 的最后步骤是步骤 4 。
示例 2：
输入：arr = [3,1,5,4,2], m = 2 输出：-1 解释： 步骤 1："00100"，由 1 构成的组：["1"] 步骤 2："10100"，由 1 构成的组：["1", "1"] 步骤 3："10101"，由 1 构成的组：["1", "1", "1"] 步骤 4："10111"，由 1 构成的组：["1", "111"] 步骤 5："11111"，由 1 构成的组：["11111"] 不管是哪一步骤都无法形成长度为 2 的一组 1 。
示例 3：
输入：arr = [1], m = 1 输出：1
示例 4：
输入：arr = [2,1], m = 2 输出：2
提示：
n == arr.length1 <= n <= 10^51 <= arr[i] <= narr中的所有整数 互不相同1 <= m <= arr.length
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1562
解题思路分析：
2020年8月24日更新：解法二
每当我们向字符串中插入一个1，理论上共有4种可能发生：
- 当前插入点左右都不是1，那么当前1会组成一个新的线段，长度为1。
- 当前插入点左边是1，右边不是1，那么当前1与左边线段组成一个新的线段，长度为左边线段长度加一。
- 与2同理，当前插入点右边是1，左边不是1，那么当前1与右边线段组成一个新的线段，长度为右边线段长度加一。
- 当前插入点左右两边都是1，那么当前1将左右两边相连，组成一个新的线段，长度为左右两边长度和再加1。
解题时，我们使用一个数组side[]来记录连续1的位置，side[i]代表以位置i开头的线段的另一端的位置。初始时，side[i]等于i。另外我们需要一个访问数组visited[]来记录每个点的访问状态，visited[i]=true代表第i个位置已经被访问过。最后，我们还需要一个变量countM来记录当前线段长度等于m的个数。
接下来我们开始循环数组中的每一个位置pos，对于上述第一种情况，side[pos]不变。第二种情况下，先查看左边线段的长度，左边线段的区间应该是side[pos-1]到pos-1。如果该长度等于m，那么长度为m的线段数量会减一（因为该长度将会与当前点合并），即countM减一。反之，如果左边线段长度加上当前点后，长度等于m的话，countM加一。同时别忘记更新side[]数组，此时，新的线段的两个端点应该是pos到side[pos-1]，因此我们需要将这两个点的互相设置为另一个点的端点。即：side[pos]=side[pos-1]，并且side[side[pos-1]]=pos。第三种情况与第二种情况类似，先看右边线段的长度，右边线段的区间应该是pos+1到side[pos+1]。如果该长度等于m，那么长度为m的线段数量会减一（因为该长度将会与当前点合并），即countM减一。反之，如果右边线段长度加上当前点后，长度等于m的话，countM加一，同时更新side数组。最后一种情况，要同时分别查看左右两边线段的长度，如果其长度等于m，countM减一。接下来左边长度与右边长度的和再加上1为合并后的长度，如果该长度加一，countM加一，同时更新side数组，此时线段俩端为side[pos-1]与side[pos+1]，因此更新side[side[pos-1]]等于side[pos+1]，并且side[side[pos+1]]等于side[pos-1]。每次循环结束前，如果countM大于0，那么当前步骤下依旧存在长度为m的线段。更新当前步骤为返回结果。
实现代码：
public int findLatestStep(int[] arr, int m) {
int[] side = new int[arr.length+1]; // 下标i为线段起点，side[i]为线段终点
for(int i=0;i<side.length;i++) side[i]=i; // 初始化，每个位置是一条线段
boolean[] visited = new boolean[arr.length+1]; // 访问数组
int countM=0; // 当前长度为m的线段数
int lastStep=-1; // 返回结果
for(int i=0;i<arr.length;i++){ // 循环每一个位置
int num=arr[i]; // 当前位置
visited[num]=true; // 设当前位置为已访问
boolean visitedLeft=(num>1&&visited[num-1]); // 查看左边是否访问过（是否为1）
boolean visitedRight=(num<arr.length&&visited[num+1]); // 查看右边是否访问过（是否为1）
if(visitedLeft&&!visitedRight){ // 如果左边是1，右边不是1
int leftLength=(num-1)-side[num-1]+1; // 左边线段长度
int newCount=leftLength+1; // 与当前位置组成的新长度
if(leftLength==m) countM--; // 如果左边线段长度为m，countM减一
if(newCount==m) countM++; // 如果当前线段长度为m，countM加一
// 当前线段两个端点分别是num与side[num-1]
side[num]=side[num-1]; // 设置num的另一个端点为side[num-1]
side[side[num-1]]=num; // 设置side[num-1]的另一个端点为num
}else if(!visitedLeft&&visitedRight){ // 如果左边不是1，右边是1
int rightLength=side[num+1]-(num+1)+1;
int newCount=rightLength+1;
if(rightLength==m) countM--;
if(newCount==m) countM++;
side[num]=side[num+1];
side[side[num+1]]=num;
}else if(visitedLeft&&visitedRight){ // 如果左边右边都是1
int leftLength=(num-1)-side[num-1]+1;
int rightLength=side[num+1]-(num+1)+1;
int newCount=leftLength+rightLength+1;
if(leftLength==m) countM--;
if(rightLength==m) countM--;
if(newCount==m) countM++;
int leftSide=side[num+1];
int rightSide=side[num-1];
side[side[num+1]]=rightSide;
side[side[num-1]]=leftSide;
}else{ // 如果左边右边都不是1
if(m==1) countM++;
}
if(countM>0) lastStep=i+1; // 如果当前countM大于0，更新当前步骤为返回结果
}
return lastStep;
} 本题解法执行时间为11ms。
Runtime: 11 ms, faster than 100.00% of Java online submissions for Find Latest Group of Size M.
Memory Usage: 48 MB, less than 100.00% of Java online submissions for Find Latest Group of Size M.
以上为更新内容
周赛时，我第一直觉便想到了Union-find思路。但转念又想到了二分查找，最终还是采用二分的方式解出了本题。但效率上并不是最优，后续还要优化。
接下来说下本题的思路。我们每进行一步，实际上会形成多个由1组成的连续区间，我们要想方设法不断的记录下每一个区间以及其后续的变化情况，才能得知最后一个长度为m的区间会在何时消失（最后步骤）。这样做显然计算量非常大。因此我们可以反过来思考。最终，所有的位置都将会变成1，我们移除最后一步操作后，最后一步操作的位置上的1会退回为0，这时，我们用0将其分割成了2部分，剩下这两部分的长度如果任何一边等于m的话，那么当前这步即是最后一步。这样问题就变得稍微简单了一些，实际上，我们是在不停的使用0将二进制字符串分割，当前分割点与左右相邻最近的0之间会形成2个新的线段，而这两段的距离如果等于m的话，那么当前步骤即是返回结果。所以，我们要重点求出左右相邻的0的位置。这里就要使用到二分查找了。
我们使用一个List记录已经分割过的位置（为0的点），其中List内元素为升序排列。我们从数组arr的最后一位向前循环，对于当前位置，我们使用二分查找在List中找到第一个小于它的数值所在下标leftIndex（这个二分查找方式是我们之前总结过的二分类型中的第三类，参考：LEETCODE常见算法之二分查找超详细白话讲解），list.get(leftIndex)即是左边第一个相邻的0在二进制字符串中的位置，另外，由于题目中不存在重复位置，因此，list中leftIndex+1位置的元素即是右边第一个相邻的0的位置rightIndex。这里注意下List下标越界问题，如果这两个位置不存在（leftIndex或者rightIndex >= list.size()），即代表，当前分割点左边或者右边不存在0。那么，当前位置减一到数组最左端或者当前位置加一到数组最右端为一个完整的全1区间。通常情况下，当前位置减一到leftIndex做代表位置以及前位置加一到rightIndex所代表位置为两个新生成的全1区间。我们分别查看这两个区间的长度，如果等于m，返回当前步骤。返回，则将当前分割点插入到rightIndex处，继续重复上述操作。
以下代码效率不高，有待改善。仅供参考。
实现代码：
public int findLatestStep(int[] arr, int m) {
// 如果m等于数组长度，那么必须执行完所有步骤。返回m。
if(m==arr.length) return m;
List<Integer> visited = new ArrayList<>(); // 记录执行过的点
for(int i=arr.length-1;i>=0;i--){ // 倒序反向执行操作，即当前点右1变0
// 从执行过的点中找到左边第一个0在visited中所在的下标
int smallIndex=findFirstSamller(visited,arr[i]);
int small=0; // 左边第一个0所在的位置
// 如果该下标存在，查看左边第一个0所在的位置
if(smallIndex!=-1) small=visited.get(smallIndex);
// 如果当前位置到small间的距离为m，返回当前步骤
if(arr[i]-small-1==m) return i;
// 当前位置右边第一个0在visited中所在的下标
int bigIndex=smallIndex+1;
int big=arr.length+1; // 右边第一个0所在的位置
// 如果该下标存在，查看右边第一个0所在的位置
if(bigIndex<visited.size()){
big=visited.get(bigIndex);
}
// 如果当前位置到big间的距离为m，返回当前步骤
if(big-arr[i]-1==m) return i;
// 将当前位置按顺序插入到visited中
visited.add(bigIndex,arr[i]);
}
return -1;
}
int findFirstSamller(List<Integer> visited, int target){
int low=0, high=visited.size()-1;
while(low<=high){
int mid=(low+high)/2;
if(visited.get(mid)<=target){
low=mid+1;
}else{
high=mid-1;
}
}
return high==visited.size()?-1:high;
} 本题解法执行时间为1387ms。
Runtime: 1387 ms, faster than 20.00% of Java online submissions for Find Latest Group of Size M.
Memory Usage: 110.3 MB, less than 20.00% of Java online submissions for Find Latest Group of Size M.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1562-find-latest-group-of-size-m-解题思路分析/