问题描述
给定一个只包含小写字母的字符串，要求去除其中重复的字母，返回保留原先字母顺序的最小字典序的字符串。题目链接：**点我**
样例输入输出
输入：”bcabc”
输出：”abc”
输入：”cbacdcbc”
输出：”acdb”
问题解法
使用栈，遍历字符串，对每个字符进行以下判断：如果栈中元素包含了当前元素，则跳过当前元素继续下一个字符的判断；如果栈不为空，则取出栈顶的元素与当前字符进行判断，如果比当前字符大并且在当前字符后面还存在栈顶的字符，则将栈顶的字符弹出，直到栈顶字符比当前字符小或栈为空时停止，然后将当前元素入栈。最后栈中的元素序列就是求解的值。此解法参考：https://leetcode-cn.com/problems/remove-duplicate-letters/solution/qu-chu-zhong-fu-zi-mu-by-leetcode/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution
{
public String removeDuplicateLetters(String s)
{
int[] charCounts = new int[26];
for (char ch : s.toCharArray())
{
charCounts[ch - 'a']++;
}
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray())
{
charCounts[ch - 'a']--;
if (stack.contains(ch))
{
continue;
}
while (!stack.isEmpty() && stack.peek() > ch && charCounts[stack.peek() - 'a'] > 0)
{
stack.pop();
}
stack.push(ch);
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty())
{
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
|
参考资料
https://leetcode-cn.com/problems/remove-duplicate-letters/solution/qu-chu-zhong-fu-zi-mu-by-leetcode/