316. 去除重复字母

原创
2020/12/28 10:24
阅读数 41

题目描述

题目思路

  1. 对于数组去重,首先想到的应该是借助Java中的Set集合进行去重,然而由于Set集合是无序的,题目又要求需要保持结果的字典序,因此无法满足要求。

  2. 因此我们可以借助栈来进行排序,对字符串遍历的时候,如果栈中没有元素,我们把元素推入栈中,每次推入栈中的元素需要与之前推入的元素进行比较,如果当前元素大于栈顶元素,则把栈顶元素弹出,继续向前找,直到无法找到为止,然后推入当前元素。

  3. 对于2情况,会出现一种问题,如果当前元素之后再也没有栈顶元素,然而我们却把栈顶元素弹出了,那么最终获得的元素就不满足要求,因此在2的弹出元素的过程中,我们需要判断后续是否还有该元素,如果有,弹出栈顶元素,如果没有当前元素直接入栈。

解题代码


/**
 * @description:
 * @author: lilang
 * @version:
 * @modified By:1170370113@qq.com
 */
public class StringSolution {

    public String removeDuplicateLetters(String s) {

        if (s == null || s.length() == 0) {
            return null;
        }

        int[] charCounts = new int[128];

        /**
         * 统计各个字符串的字数
         */
        for (char sc : s.toCharArray()) {

            charCounts[sc]++;
        }

        Stack<Character> stackSc = new Stack<Character>();

        boolean[] instack = new boolean[128];

        for (char sc : s.toCharArray()) {

            charCounts[sc]--;

            if (instack[sc]) {
                continue;
            }
            /**
             * 准备遍历栈
             */
            while (!stackSc.isEmpty() && stackSc.peek() > sc) {

                //如果当前元素后面没有元素了,则不再进行弹出
                if (charCounts[stackSc.peek()] == 0) {
                    break;
                }
                instack[stackSc.pop()] = false;

            }

            stackSc.push(sc);

            instack[sc] = true;

        }

        StringBuffer stringBuffer = new StringBuffer();
        while (!stackSc.isEmpty()) {
            stringBuffer.append(stackSc.pop());

        }

        return stringBuffer.reverse().toString();
    }
    
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部