我是做废品回收，最近有个变宝网主动联系我说是再生资源网站的，可信吗？,wordpress 什么语言,58同城网站官网,网站建设制度本文是力扣LeeCode-316. 去除重复字母 学习与理解过程#xff0c;本文仅做学习之用#xff0c;对本题感兴趣的小伙伴可以出门左拐LeeCode。 给你一个字符串 s #xff0c;请你去除字符串中重复的字母#xff0c;使得每个字母只出现一次。需保证 返回结果的字典序最小#…本文是力扣LeeCode-316. 去除重复字母 学习与理解过程本文仅做学习之用对本题感兴趣的小伙伴可以出门左拐LeeCode。 给你一个字符串 s 请你去除字符串中重复的字母使得每个字母只出现一次。需保证 返回结果的字典序最小要求不能打乱其他字符的相对位置。 示例 1 输入s “bcabc” 输出“abc” 示例 2 输入s “cbacdcbc” 输出“acdb” 提示 1 s.length 104 s 由小写英文字母组成 注意该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同 思路
初做这道题我一下子就想到了之前有做过 1047. 删除字符串中的所有相邻重复项 题使用栈方法移除相同项这道题显然也可以这样做一部分但是由于这道题要求有三个
去重去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序字典序最小
笔者这边做完去重和不打乱字符出现的相对顺序后发现对这道题的要求3束手无策了。于是参考了LeeCode博主labuladong对这道题的题解我才发现还可以遇山开山遇河架桥666。下面是我对博主题解的简述和总结
要求1和2可以直接用如下代码解决
String removeDuplicateLetters(String s) {// 存放去重的结果StackCharacter stack new Stack();// 布尔数组初始值为 false记录栈中是否存在某个字符// 输入字符均为 ASCII 字符所以大小 256 够用了boolean[] inStack new boolean[256];for (char c : s.toCharArray()) {// 如果字符 c 存在栈中直接跳过if (inStack[c]) continue;// 若不存在则插入栈顶并标记为存在stack.push(c);inStack[c] true;}StringBuilder sb new StringBuilder();while (!stack.empty()) {sb.append(stack.pop());}// 栈中元素插入顺序是反的需要 reverse 一下return sb.reverse().toString();
}以bcabc举例这个算法会返回 “bca”已经符合要求1和要求2但是题目希望要的答案是 “abc” 。所以此时需要考虑要求3如何让字典项最小以a、b、c、……举例c的ASCII值大于bb的ASCII值大于a如果b比a先进栈就需要先将b出栈popa才可以进栈排前面如果c比b先进栈就需要先将c出栈popb才可以进栈排前面…… 是否很像单调栈的原理
String removeDuplicateLetters(String s) {StackCharacter stack new Stack();boolean[] inStack new boolean[256];for (char c : s.toCharArray()) {if (inStack[c]) continue;// 插入之前和之前的元素比较一下大小// 如果字典序比前面的小pop 前面的元素while (!stack.isEmpty() stack.peek() c) {// 弹出栈顶元素并把该元素标记为不在栈中inStack[stack.pop()] false;}stack.push(c);inStack[c] true;}StringBuilder sb new StringBuilder();while (!stack.empty()) {sb.append(stack.pop());}return sb.reverse().toString();
}对于以上代码我们输入 s bcabc我们可以得出正确结果 abc 了,但是对于sbcac,结果是ac,结果是不对的。究其根本在于我们一杆子打死了所有stack.peek() c 的情况。以 s bcac为例我们没有考虑到将b出栈后后续字符串中有没有b了c是没问题的它后面还有所以我们需要分情况讨论
如果 stk.peek() 这个字符之后还会出现那么可以把它 pop 出去后面再 push 到栈里即可如果 stk.peek() 这个字符之后不会出现了那么就不能把它 pop 出去否则无法在后面找它了
该怎么实现这个效果呢 计数器统计
最终代码实现
class Solution {public String removeDuplicateLetters(String s) {StackCharacter stack new Stack();boolean[] inStack new boolean[256];// 维护一个计数器记录字符串中字符的数量// 因为输入为 ASCII 字符大小 256 够int[] count new int[256];for(char a : s.toCharArray()){count[a];}for(char c : s.toCharArray()){count[c]--; // 每遍历过一个字符都将对应的计数减一if(inStack[c])continue;while(!stack.isEmpty()stack.peek()c){// 如果之后不存在栈顶元素了则停止 popif(count[stack.peek()]0)break;// 如果之后还有则可以大胆 popinStack[stack.pop()] false;}stack.push(c);inStack[c] true;}StringBuilder sb new StringBuilder();while(!stack.isEmpty()){sb.append(stack.pop());}return sb.reverse().toString(); }
}时间复杂度: O(N) 空间复杂度: O(N) 大佬们有更好的方法请不吝赐教谢谢。
