单调栈
去除重复字母(316)
题目解析:
- 我们每次都找到当前能够移到最左边的、最小的字母。
- 要求:
-
- 最小
-
- 最左边
- 右边如果还有重复的，就不算
思路:
栈 👍
通过栈来保存最小的数据，单调递增栈。每次入栈的时候，和栈顶判断下，判断当前值和栈顶比对是否更小，并且栈顶后面是否还有重复值，如果有，则出栈。
public String removeDuplicateLetters(String s) {
// 保存结果，栈低是最小值
Stack<Character> stack = new Stack<>();
// 是否已经有在栈里，如果已经处理，则不处理。
HashSet<Character> seen = new HashSet<>();
// 用来判断，当前最后出现的位置。如果后续没有重复的值了(即是最后一个了)，则不能出栈。
HashMap<Character, Integer> last_occur = new HashMap<>();
for (int i = 0; i < s.length(); i++){
last_occur.put(s.charAt(i), i);
}
// 遍历字符串，判断是否入栈
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if (!seen.contains(c)){
while (!stack.isEmpty() &&
c < stack.peek() &&
last_occur.get(stack.peek()) > i){
seen.remove(stack.pop());
}
seen.add(c);
stack.push(c);
}
}
// 将栈中元素保存成字符串输出
StringBuilder sb = new StringBuilder(stack.size());
for (Character c: stack){
sb.append(c.charValue());
}
return sb.toString();
}
- 时间复杂度：O(N)。虽然看起来是双重循环，但内循环的次数受栈中剩余字符总数的限制，因为栈中的元素不重复，不会超出字母表大小，因此最终复杂度仍为 O(N)。
- 空间复杂度：O(1)。看上去空间复杂度像是 O(N)，但实际上并不是。首先，seen 中字符不重复，其大小会受字母表大小的限制，所以是O(1)。其次，只有 stack 中不存在的元素才会被压入，因此 stack 中的元素也唯一。所以最终空间复杂度为 O(1)。
贪心算法
我们每次都找到当前能够移到最左边的、最小的字母。这就是我们得到结果的第一个字母，它之前的所有重复字母会被删掉；然后我们从它以后的字符串中，使用相同的逻辑，继续寻找第二个最小的字母。
所以，我们在代码实现上，可以使用递归
public class RemoveDuplicateLetters {
public String removeDuplicateLetters(String s) {
if (s.length() == 0) return "";
int position = 0;
for (int i = 0; i < s.length(); i++){
if (s.charAt(i) < s.charAt(position)){
boolean isReplaceable = true;
for (int j = position; j < i; j++){
boolean isDuplicated = false;
for (int k = i; k < s.length(); k++){
if (s.charAt(k) == s.charAt(j)){
isDuplicated = true;
break;
}
}
isReplaceable = isReplaceable && isDuplicated;
}
if (isReplaceable){
position = i;
}
}
}
return s.charAt(position) + removeDuplicateLetters0(s.substring(position+1).replaceAll(""+s.charAt(position), ""));
}
}- 时间复杂度：O(N^3)，因为用到了三重循环，最坏情况下时间复杂度达到了N^3。（超出运行时间限制）
- 空间复杂度：O(N)，每次给字符串切片都会创建一个新的字符串（字符串不可变），切片的数量受常数限制，最终复杂度为 O(N) * C = O(N)
贪心算法改进版
我们发现，对于“是否重复出现”的判断，每次都要偏离当前字母之后的所有字符，这显然做了很多重复工作。
优化的方法，我们可以用一个count数组，保存所有26个字母在s中出现的频次。当我们遍历字符串时，每遇到一个字母，就让它对应的count减一；当当前字母对应的count减为0时，说明之后不会再重复出现了，因此即使有更小的字母也不能替代它，我们直接就可以把它作为最左侧字母输出了
public String removeDuplicateLetters(String s) {
if (s.length() == 0) return "";
int position = 0;
// 定义一个count数组，用来保存26个字母在s中出现的频次
int[] count = new int[26];
for (int i = 0; i < s.length(); i++){
count[s.charAt(i) - 'a'] ++;
}
for (int i = 0; i < s.length(); i++){
if (s.charAt(i) < s.charAt(position)) {
position = i;
}
if (--count[s.charAt(i) - 'a'] == 0){
break;
}
}
return s.charAt(position) +
removeDuplicateLetters(s.substring(position+1)
.replaceAll("" + s.charAt(position), ""));
}- 时间复杂度：O(N)。 每次递归调用占用 O(N) 时间。递归调用的次数受常数限制(只有26个字母)，最终复杂度为 O(N) * C = O(N)。
- 空间复杂度：O(N)，每次给字符串切片都会创建一个新的字符串（字符串不可变），切片的数量受常数限制，最终复杂度为 O(N) * C = O(N)。