题目描述
题目思路
-
对于数组去重，首先想到的应该是借助Java中的Set集合进行去重，然而由于Set集合是无序的，题目又要求需要保持结果的字典序，因此无法满足要求。
-
因此我们可以借助栈来进行排序，对字符串遍历的时候，如果栈中没有元素，我们把元素推入栈中，每次推入栈中的元素需要与之前推入的元素进行比较，如果当前元素大于栈顶元素，则把栈顶元素弹出，继续向前找，直到无法找到为止，然后推入当前元素。
-
对于2情况，会出现一种问题，如果当前元素之后再也没有栈顶元素，然而我们却把栈顶元素弹出了，那么最终获得的元素就不满足要求，因此在2的弹出元素的过程中，我们需要判断后续是否还有该元素，如果有，弹出栈顶元素，如果没有当前元素直接入栈。
解题代码
/**
* @description:
* @author: lilang
* @version:
* @modified By:1170370113@qq.com
*/
public class StringSolution {
public String removeDuplicateLetters(String s) {
if (s == null || s.length() == 0) {
return null;
}
int[] charCounts = new int[128];
/**
* 统计各个字符串的字数
*/
for (char sc : s.toCharArray()) {
charCounts[sc]++;
}
Stack<Character> stackSc = new Stack<Character>();
boolean[] instack = new boolean[128];
for (char sc : s.toCharArray()) {
charCounts[sc]--;
if (instack[sc]) {
continue;
}
/**
* 准备遍历栈
*/
while (!stackSc.isEmpty() && stackSc.peek() > sc) {
//如果当前元素后面没有元素了，则不再进行弹出
if (charCounts[stackSc.peek()] == 0) {
break;
}
instack[stackSc.pop()] = false;
}
stackSc.push(sc);
instack[sc] = true;
}
StringBuffer stringBuffer = new StringBuffer();
while (!stackSc.isEmpty()) {
stringBuffer.append(stackSc.pop());
}
return stringBuffer.reverse().toString();
}
}
