LeetCode刷题——去除重复字母#316#Medium

去除重复字母的思路探讨与源码
    去除重复字母的题目如下图，该题属于字符串类和栈搜索类型的题目，主要考察对于字符串搜索方法的使用和栈结构的理解。本文的题目作者想到2种方法，分别是贪心单调栈方法和哈希表方法，其中贪心单调栈方法使用Java进行编写，而哈希表方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用贪心单调栈方法的思路进行解决，首先初始化一个长度26位的布尔类型的数组并赋值。然后初始化一个字符串列表，开始遍历循环，将当前下标对应的字符拿出来，将它和小写字母a进行比较，如果没有遍历过，那么就进行搜索，如果满足条件就将布尔类型的值赋值为false后删除这个字符，即认为是重复。再将结果插入到字符串列表里，以此逻辑循环并直到结束后返回结果。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    public String removeDuplicateLetters(String s) {
        boolean[] numCharArr = new boolean[26];
        int[] num = new int[26];
        for (int ir = 0; ir < s.length(); ir++) {
            num[s.charAt(ir) - 'a']++;
        }

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (! numCharArr[ch - 'a']) {
                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
                    if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        numCharArr[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    } else {
                        break;
                    }
                }
                numCharArr[ch - 'a'] = true;
                sb.append(ch);
            }
            num[ch - 'a'] -= 1;
        }
        return sb.toString();
    }
}

    显然，我们看到贪心单调栈方法的效果还可以，同时还可以使用哈希表的方法解决。首先初始化一个计数器和一个队列，计数器可以得到每个字符出现的次数，然后开始遍历字符串，将当前字符的数量减去1，并且判断字符是否在列表里，如果是就继续下一轮循环，如果不是就会循环遍历列表，把列表的元素抛出后，将当前字符加入到列表里面，最终直到循环结束并返回列表的所有元素的和，即最终的字符串。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
from collections import Counter
class Solution:
    def removeDuplicateLetters(self, s):
        listStack=[]
        sk = Counter(s)
        for jr in s:
            sk[jr] = sk[jr]-1
            if(jr in listStack):
                continue
            while listStack and listStack[-1] > jr and sk[listStack[-1]] > 0:
                    listStack.pop()
            listStack.append(jr)
        return ''.join(listStack)

    从结果来说Java版本的贪心单调栈的效率还可以，而Python版本的哈希表方法的速度比较一般，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。