网站关键词是什么,山东seo推广网站建设,江西省赣州市教育局,网站怎么做百度地图给你一个字符串 s #xff0c;请你去除字符串中重复的字母#xff0c;使得每个字母只出现一次。需保证 返回结果的字典序最小#xff08;要求不能打乱其他字符的相对位置#xff09;。 示例 1#xff1a; 输入#xff1a;s “bcabc” 输出#xff1a;“abc” 示例 2请你去除字符串中重复的字母使得每个字母只出现一次。需保证 返回结果的字典序最小要求不能打乱其他字符的相对位置。 示例 1 输入s “bcabc” 输出“abc” 示例 2 输入s “cbacdcbc” 输出“acdb” 提示
1 s.length 10^4 s 由小写英文字母组成 解题思路
1、大于O(n ^ 2)时间复杂度的算法会超时
2、由于要输出字典序最小的排列所以字典序越小的字符就我设法让其排在前面这就是贪心思维
3、需要栈辅助即栈顶元素比添加进来的元素大那么设法消掉此栈顶元素
4、需要index数组保留字符最后一次出现的位置以便删掉栈顶元素使用
5、需要boolean类型数组判断新添元素是否在栈内存在 代码
class Solution {public String removeDuplicateLetters(String s) {char a[] s.toCharArray();int len a.length;int index[] new int [26]; for(int i 0; i len; i ) index[a[i] - a] i;//记录每个字母最后出现的位置boolean check[] new boolean [26];DequeCharacter stack new ArrayDeque();for(int i 0; i len; i ) {if(!check[a[i] - a]) {//如果栈内没有就选择添加while(!stack.isEmpty() stack.peekLast() a[i] index[stack.peekLast() - a] i) {//如果添加的元素比栈顶小char c stack.removeLast();check[c - a] false;}stack.add(a[i]);check[a[i] - a] true;}}StringBuffer s1 new StringBuffer();for(char d : stack) s1.append(d);return s1.toString();}
}
