LeetCode 去除重复字母【贪心】【栈】

深藏阁楼爱情的钟 2022-09-10 08:22 166阅读 0赞

# 1 去除重复字母 #

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

示例 1：

输入：s = "bcabc"
    输出："abc"

示例 2：

输入：s = "cbacdcbc"
    输出："acdb"

提示：

1 <= s.length <= 104
    s 由小写英文字母组成

# 2 解题思路 #

## 2.1 递归（超时） ##

/** * 每次找字典序最小位置，然后递归调用 */
        public String removeDuplicateLetters(String s) { 
            if (s == null || s.length() == 0) { 
                return "";
            }
    
            //假设字典序最小位置为初始位置
            int position = 0;
    
            for (int i = 0; i < s.length(); i++) { 
                //如果当前i字典序小于position，需要判断是否能替换,替换条件必须满足i之前所有元素在i之后也出现过
                if (s.charAt(position) > s.charAt(i)) { 
                    //假设能够替换
                    boolean isReplace = true;
                    for (int j = position; j < i; j++) { 
                        boolean isFind = false;
                        char a = s.charAt(j);
                        for (int k = i + 1; k < s.length(); k++) { 
                            if (a == s.charAt(k)) { 
                                isFind = true;
                                break;
                            }
                        }
                        if (!isFind) { 
                            isReplace = false;
                            break;
                        }
    
                    }
                    if (isReplace) { 
                        position = i;
                    }
                }
            }
            //截取 position 后面的字符
            String substring = s.substring(position + 1);
            //替换字符已经出现过的最小字典序
            char target = s.charAt(position);
            String replaceStr = substring.replaceAll(String.valueOf(target), "");
            return target + removeDuplicateLetters(replaceStr);
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

## 2.2 递归 （优化查找） ##

**解析：** 如果当前i字典序小于position，需要判断是否能替换,替换条件必须满足i之前所有元素在i之后也出现过，这里采用3层循环，可以优化。

public String removeDuplicateLetters(String s) { 
            if (s == null || s.length() == 0) { 
                return "";
            }
    
            //打标
            char[] chars = new char[26];
            for (int i = 0; i < s.length(); i++) { 
                chars[s.charAt(i) - 'a']++;
            }
    
            //假设字典序最小位置为初始位置
            int position = 0;
            for (int i = 0; i < s.length(); i++) { 
                //如果当前i字典序小于position，需要判断是否能替换,替换条件必须满足i之前所有元素在i之后也出现过
                if (s.charAt(position) > s.charAt(i)) { 
                    position = i;
                }
                //如果当前position等于0，表示唯一，不可能重复
                if (--chars[s.charAt(i) - 'a'] <= 0) { 
                    break;
                }
    
            }
            //截取 position 后面的字符
            String substring = s.substring(position + 1);
            //替换字符已经出现过的最小字典序
            char target = s.charAt(position);
            String replaceStr = substring.replaceAll(String.valueOf(target), "");
            return target + removeDuplicateLetters(replaceStr);
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 2.3 栈 ##

public String removeDuplicateLetters(String s) { 
    
            if (s.length() == 1) { 
                return s;
            }
    
            //记录已经选过的
            boolean[] selected = new boolean[26];
    
            //打表，判断后面是否还有
            int[] counts = new int[26];
            for (int i = 0; i < s.length(); i++) { 
                counts[s.charAt(i) - 'a']++;
            }
    
            //用栈特性来处理，把最小的压栈
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) { 
                char temp = s.charAt(i);
                // 如果没有选择
                if (!selected[temp - 'a']) { 
                    //判断当前栈顶是否小于temp
                    while (!stack.isEmpty() && stack.peek() > temp) { 
                        Character peek = stack.peek();
                        //判断当前栈顶字母后面是否还会出现
                        if (counts[peek - 'a'] > 0) { 
                            stack.pop();
                            selected[peek - 'a'] = false;
                        } else { 
                            break;
                        }
    
                    }
                    stack.push(temp);
                    selected[temp - 'a'] = true;
                }
    
                counts[temp - 'a']--;
            }
    
            StringBuilder sb = new StringBuilder();
    
            for (Character c : stack) { 
                sb.append(c);
            }
            return sb.toString();
    
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/255afc5c2b024b7b96a42463f3c8d6df.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/dd0af6fb278a4979bf283f3571eb12fb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/fa4378ec05d04f569674f72c012abe24.png