题目大意：
删除字符串中的所有相邻重复项 II
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
本题答案保证唯一。
示例 1：
输入：s = "abcd", k = 2 输出："abcd" 解释：没有要删除的内容。
示例 2：
输入：s = "deeedbbcccbdaa", k = 3 输出："aa" 解释： 先删除 "eee" 和 "ccc"，得到 "ddbbbdaa" 再删除 "bbb"，得到 "dddaa" 最后删除 "ddd"，得到 "aa"
示例 3：
输入：s = "pbbcggttciiippooaais", k = 2 输出："ps"
提示：
1 <= s.length <= 10^52 <= k <= 10^4s中只含有小写英文字母。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1209
解题思路分析：
这是一道典型使用Stack来求解的题目。循环字符串的每一个字符，如果当前字符与Stack中最后插入的字符不同，那么将当前字符插入到Stack中。如果相同，便要查看Stack中最后连续相同字符的长度加上当前字符是否等于题目给出的k，如果等于则将Stack中最后相同的部分pop出来。如果未达到k的长度，则将当前字符加入到Stack中。重复执行此步骤直到循环结束。
为了方便查看Stack最后有多少连续字符与当前字符相同，我们可以在新建另外一个Stack，保存最后连续相同字符的长度。
细节实现可以看下完整代码：
public String removeDuplicates(String s, int k) {
Stack<Character> stack = new Stack<>(); // 排重的Stack
Stack<Integer> stackLength = new Stack<>(); // 记录连续相同字符长度的Stack
for(int i=0;i<s.length();i++){ // 循环每一个字符
char c = s.charAt(i); // 当前字符
// Stack为空或者当前字符与Stack上次插入的字符不相同
if(stack.size()==0 || c != stack.peek()){
stack.push(c); // 将当前字符插入到stack
stackLength.push(1); // 当前字符连续长度为1
}else{ // 当前字符与stack中前字符相同
int sameLength = stackLength.pop()+1; // 连续相同字符的长度
if(sameLength == k){ // 如果长度为k
for(int j=1;j<k;j++){ // 删除连续相同的字符
stack.pop();
}
}else{ // 长度小于k
// 更新连续相同字符长度
stackLength.push(sameLength);
stack.push(c); // 将当前字符加入到stack
}
}
}
// 将stack剩下的元素组成返回值。注意需要反转字符串
StringBuilder res=new StringBuilder();
while(stack.size()>0){
res.append(stack.pop());
}
return res.reverse().toString();
} 本题是典型的Stack题目。如果将Stack变成数组来实现将大幅提高运行速度。这里为了方便理解，并没有做出上述优化。
本题解法运行时间为39ms。
Runtime: 39 ms, faster than 36.81% of Java online submissions for Remove All Adjacent Duplicates in String II.
Memory Usage: 38.4 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates in String II.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1209-remove-all-adjacent-duplicates-in-string-ii-解题思路分析/