leetCode-316:Remove Duplicate Letters

问题描述

给定一个只包含小写字母的字符串,要求去除其中重复的字母,返回保留原先字母顺序的最小字典序的字符串。题目链接:点我

样例输入输出

输入:”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/