5分钟一个算法编程小点：顺序去重

缺乏、安全感 2022-12-29 06:38 21阅读 0赞

### 题目：316. 去除重复字母 ###

要求去重字符串中的字符，还要保留字符原本中的顺序，第一点好理解，第二天不太好理解，什么意思呢？

*  bcabc  
    b、c 要去掉一个，保留原本的顺序，得到最小的字符串，应该是后缀三个字符 ：abc
 *  bcadbc  
    答案是adbc，这里主要在d的位置已经固定，不能打乱原本字符在输入字符中的位置

### 解法：数组+栈 ###

这里涉及到两个数组，一个数组来标示那些已经字符访问过了，另一个字符来标示字符数量，通过栈的特性：后进先出的特点，从前到后比较数据，如果碰到字符比较小的数据，栈就自动pop字符，一直到比pop 字符还要小的情况，

*  特殊情况：考虑到有些字符只出现一次，所以即使栈中字符要比新字符大也不会pop出数据

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhbmRvbXBlb3BsZQ_size_16_color_FFFFFF_t_70]

### 代码 ###

class Solution {
        public String removeDuplicateLetters(String s) {
            boolean[] vis = new boolean[26];
            int[] num = new int[26];
            for (int i = 0; i < s.length(); i++) {
                num[s.charAt(i) - 'a']++;
            }
            Deque<Character> stack = new ArrayDeque<Character>();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (!vis[ch - 'a']) {
                // 开始 跟栈中的数据比较
                    while(stack.size()>0){
                        char ab = stack.getFirst();
                        if(num[ab- 'a']==0 || ab<ch){
                            break;
                        }
                        vis[ab-'a']=false;
                        stack.pop();
                    }
                    stack.push(ch);
                    vis[ch-'a']=true;
                }
                num[ch - 'a'] -= 1;
            }
            // 遍历栈中数据
            String res = "";
            while(stack.size()>0){
                res=stack.pop()+res;
            }
            return res;
        }
    }

### 题目 ###

[去除重复字母 中等难度][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhbmRvbXBlb3BsZQ_size_16_color_FFFFFF_t_70]: /images/20221120/ec6801b774e148fba49a28e8b8157fde.png
[Link 1]: https://leetcode-cn.com/problems/remove-duplicate-letters/