D.二分查找－二分答案－求最大——1898. 可移除字符的最大数目

题目链接：1898. 可移除字符的最大数目（中等）

算法原理：

此题的题意跟下面这题基本一模一样👇，只不过之前的求最小，这个是求最大

D.二分查找－二分答案－求最小——3639. 变为活跃状态的最小时间

解法：二分查找

96ms击败40.00%

时间复杂度O(Nlogn)

①目标变量：依次移除下标数

②目标条件：在保证p是否还是剩下子串的子序列的前提下，尽量多移除下标

③转换逻辑：移除前mid个下标对应的字符后，p是否还是剩下子串的子序列

具体步骤：

①确定边界：

left：0，最少就是一个都不移除

right：removable.length，最多就是把removable数组中的下标全移除

②确定二分模型：

移除下标数↑ p是剩余子串的子序列的概率↓ 呈负相关单调，由于是找最大移除下标数，因此采用最右端点模型

③check方法设计：

如果移除了mid个下标，如果p还是剩下子串的子序列就返回true，mid不动地方，否则就是移除多了，需要向左调整，这里我们采用标记数组，如果s数组中的字符被移除就标记为true，遍历时从左向右依次检查，如果未被移除，且能和p中字符对应，就相应指针往后挪，继续检查，当指针恰好把p走完，说明还有p的这个子序列

答疑

Q1：既然是一一对应检查，我把s和p都存进顺序表检查不可以吗？

有的小伙伴写check方法时可能会想到用顺序表，给s和p分别创建一个顺序表，利用Java自带的ArrayList移除中间元素后，后续元素会自动向前拼接的特性来判断s剩余字符串是否还存在子序列p，相关代码放下面了，但这有个致命错误，那就是下标偏移错误，举个例子👇

假设原始 s = "abcde"（下标 0-4），r = [2, 3]（要移除原始下标 2 和 3，对应字符 'c' 和 'd'）
第一步：tmp.remove(2) → tmp 变成 ["a","b","d","e"]（原始 'd' 现在在 tmp 的下标 2 位置）
第二步：tmp.remove(3) → 你想删原始下标 3 的 'd'，但现在 tmp 的下标 3 是 'e'，结果删成了 'e'，完全错了

Java代码：

class Solution { public int maximumRemovals(String s, String p, int[] r) { int left=0,right=r.length; while(left<right){ int mid=left+(right-left+1)/2; if(!check(mid,s,p,r)) right=mid-1; else left=mid; } return left; } //移除前mid个下标对应字符后，子序列还有p就返回true private boolean check(int mid,String s, String p, int[] r){ int n=s.length(); boolean[] removed=new boolean[n]; for(int i=0;i<mid;i++) removed[r[i]]=true; int pindex=0; for(int i=0;i<n&&pindex<p.length();i++) if(!removed[i]&&s.charAt(i)==p.charAt(pindex)) pindex++; return pindex==p.length(); } }

class Solution { //错误的示范代码 private static List<Character> listp=new ArrayList<>(); private static List<Character> lists=new ArrayList<>(); public int maximumRemovals(String s, String p, int[] r) { for(char c:p.toCharArray()) listp.add(c); for(char c:s.toCharArray()) lists.add(c); int left=0,right=r.length; while(left<right){ int mid=left+(right-left+1)/2; if(!check(mid,r)) right=mid-1; else left=mid; } //个数=下标+1 return left+1; } //移除前mid个下标对应字符后，子序列还有p就返回true private boolean check(int mid,int[] r){ List<Character> tmp=new ArrayList<>(lists); int index=0; for(int i=0;i<mid;i++) tmp.remove(r[i]); for(char c:tmp) if(c==listp.get(index)) index++; return index==listp.size()-1; } }