当前位置：首页 > article >正文

力扣labuladong一刷day27天数组去重

article 2024/9/17 3:20:45

力扣labuladong一刷day27天数组去重

一、316. 去除重复字母

题目链接：https://leetcode.cn/problems/remove-duplicate-letters/
思路：题目有三个要求：去重、保持顺序、字典序尽量小。去重的话我们可以使用一个boolean数组做标记，用过了就不能用了。
保持相对顺序还有字典序，使用栈，当前字符大于栈头，就往里加，小于的话，需要考虑是否弹出栈头，如果栈头是最后一次出现就不要谈了。

class Solution {
   public String removeDuplicateLetters(String s) {
        int[] nums = new int[26];
        boolean[] flags = new boolean[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            nums[c-'a'] += 1;
        }
        Deque<Character> stack = new LinkedList<>();
        StringBuilder builder = new StringBuilder();
        for (char c : chars) {
            int i = c-'a';
            nums[i]--;
            if (flags[i]) continue;

            while (!stack.isEmpty() && stack.peek() > c) {
                if (nums[stack.peek()-'a'] == 0) break;
                flags[stack.pop()-'a'] = false;
            }
            stack.push(c);
            flags[i] = true;
        }

        while (!stack.isEmpty()) {
            builder.append(stack.pop());
        }
        return builder.reverse().toString();
    }
}