题目描述:
给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例:
输入: "cbacdcbc"
输出: "acdb"
首先解释一下字典序。字典序是指从前到后比较两个字符串大小的方法。
首先比较第 1 个字符,如果不同则第 1 个字符较小的字符串更小;
如果相同则继续比较第 2 个字符 …… 如此继续,比较整个字符串的大小。
观察示例 1:bcabc。
字符 a 在字符串中只出现一次,根据题目要求,字符 a 必须被选取;
字符 b 出现了两次,显然选择 a后面的那个,因为字典序 ab 在 ba 前面。同理,有两个相同的字符 c ,我们选择后一个。因此,输出就是 abc。
再观察示例 2:cbacdcbc。
有 4 个字符:a、b、c、d。其中 a 和 d 只出现一次,必须被选取;
b 出现 2 次,一个在 a 前面,一个在 a 后面,显然保留在 a 后面的;
c 出现 4 次,我们把几种可能都列出来观察一下:
情况 1:cadb
情况 2:acdb(字典序最小)
情况 3:adcb
情况 4:adbc
一种最理想的情况是:abcd,在遍历的时候,遇到的字符串的 ASCII 值逐渐增大。
下面我们就思考,当遍历到的字符的 ASCII 值减少的时候,应该如何处理。
还看示例 1:已经读到了 bc,已经是字典序最小的排列。
即将读到的 a 比 c 的 ASCII 值小。如果 a 能排在 c 之前,就能得到一个比 ca 更小的字典序 ac。
那么 a 能不能排在 c 之前,就看 a 的后面还会不会出现字符 c,显然会。同理,由于字符 b 在将来还会出现,构成的字典序更小,因此舍弃之前的字符 b。
到此为止,应该想到我们需要借助栈帮助我们完成这题。
然后根据这个思路,我们再看一下示例 2:cbacdcbc。
栈.png第 1 步:读到 c,入栈,此时栈中元素 [c];
第 2 步:读到 b,b 比之前 a 小,c 在以后还会出现,因此 c 出栈,b 入栈,此时栈中元素 [b];
第 3 步:读到 a,a 比之前 b 小,b 在以后还会出现,因此 b 出栈,a 入栈,此时栈中元素 [a];
第 4 步:读到 c,c 比之前 a 大,直接让 c 入栈,此时栈中元素 [a, c];
第 5 步:读到 d,d 比之前 d 大,直接让 d 入栈,此时栈中元素 [a, c, d];
第 6 步:读到 c,这里要注意:此时栈中已经有 c 了,此时栈中元素构成的字符顺序就是最小的字典序,不可能舍弃之前的 c,而用现在的读到的 c,因此这个 c 不需要,直接跳过;
第 7 步:读到 b,b 比之前的 c 小,但是,后面不会再出现 b 了,因此 b 就应该放在这个位置,因此让 b 入栈,此时栈中元素 [a, c, d, b];
第 8 步:读到 c,同第 6 步,这个 c 我们不需要。
于是,我们可以设计如下算法:
1、遍历字符串里的字符,如果读到的字符的 ASCII 值是升序,依次存到一个栈中;
2、如果读到的字符在栈中已经存在,这个字符我们不需要;
3、如果读到的 ASCII 值比栈顶元素严格小,看看栈顶元素在后面是否还会出现,如果还会出现,则舍弃栈顶元素,而选择后出现的那个字符,这样得到的字典序更小。
因为需要判断读到的字符在栈中是否已经存在,因此可以使用哈希表,又因为题目中说,字符只会出现小写字母,用一个布尔数组也是可以的,注意在出栈入栈的时候,需要同步更新一下这个布尔数组。
又因为要判断栈顶元素在后面是否会被遍历到,因此我们需要先遍历一次字符,存一下这个字符最后出现的位置,就能判断栈顶元素在后面是否会被遍历到。
作者:liweiwei1419
链接:https://leetcode-cn.com/problems/remove-duplicate-letters/solution/zhan-by-liweiwei1419/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
Java代码:
class Solution {
public String removeDuplicateLetters(String s) {
int len = s.length();
if (len < 2) return s;
// 记录是否在已经得到的字符串中
boolean[] set = new boolean[26];
// 记录每个字符出现的最后一个位置
int[] lastAppearIndex = new int[26];
for(int i = 0;i < len;i++) {
lastAppearIndex[s.charAt(i) - 'a'] = i;
}
Deque<Character> stack = new ArrayDeque<>();
// 此时 `a` 作为哨兵,这个 `a` 永远不会被弹出
// 如此一来,在遍历的时候,就不用判断栈是否为空了
stack.push('a');
for(int i = 0;i < len;i++) {
char curChar = s.charAt(i);
if(set[curChar - 'a']) continue;
while(stack.peek() > curChar && lastAppearIndex[stack.peek() - 'a'] >= i) {
char top = stack.pop();
set[top - 'a'] = false;
}
stack.push(curChar);
set[curChar - 'a'] = true;
}
int size = stack.size();
StringBuilder result = new StringBuilder();
for(int i = 0;i < size - 1;i++) {
result.insert(0, stack.pop()); //这里用append会出错,暂时懒得查append和insert的区别了
}
return result.toString();
}
}
网友评论