leetcode 316. 중복 알파벳 제거, 문자열 무게 제거, 최소 사전 순서

leetcode 316. 중복 알파벳 제거, 문자열 무게 제거, 최소 사전 순서
제목 설명: 소문 자 만 포 함 된 문자열 을 드 립 니 다. 문자열 에 중복 되 는 자 모 를 제거 하여 모든 자모 가 한 번 만 나타 날 수 있 도록 하 십시오.결 과 를 되 돌려 주 는 사전 순서 가 가장 작 아야 합 니 다.예제 1: 입력: "bcabc" 출력: "abc" 예제 2: 입력: "cbacdcbc" 출력: "acdb"
1. 지식 점: 데이터 구조: 반복 과 무 거 운 것 은 hashset 을 생각해 야 합 니 다. hashmap 와 추가 공간 을 사용 하지 못 하면 더 블 포인터 순서 와 관련 된 문 제 를 생각해 야 합 니 다. stack 스 택 이라는 문 제 를 옮 겨 다 니 고 매 거 하려 면 비 현실 적 이 고 너무 복잡 해 야 합 니 다. 간단하게 욕심 산법 으로 욕심 산법 을 시험 해 보 세 요. 욕심 산법 (탐욕 산법) 은문 제 를 풀 때 는 항상 현재 로 서 는 가장 좋 은 선택 을 한다.즉, 전체적으로 가장 좋 은 것 을 고려 하지 않 고 그 가 한 것 은 특정한 의미 에서 부분 적 으로 가장 좋 은 것 이다.2. 기본 욕심 산법 사상: 모든 문 자 를 옮 겨 다 니 며 1. 이 문자 가 나 타 났 는 지 여 부 를 판단 합 니 다. stack 의 첫 번 째 문 자 를 먼저 넣 지 않 고 뒤에서 시작 하 는 문 자 를 옮 겨 다 니 지 않 았 다 면 2. 이 문자 가 이전 문자 보다 작 으 면 이전 문 자 를 검사 합 니 다. 앞의 문자 가 뒤에 있 으 면 이전 문자 pop 을 스 택 에서 내 보 내 현재 문자 에 넣 습 니 다.또한 스 택 에 값 이 있 으 면 이 프로 세 스 검 사 를 반복 합 니 다. 요구 에 부합 되 지 않 을 때 까지 3. 현재 문자 3. 코드 를 넣 습 니 다.

public String removeDuplicateLetters(String s) {
     
        //       ：
        //           ，
        // hashmap             ，
        // set          
        Stack<Character> stack=new Stack<>();
        Map<Character,Integer> map=new HashMap<>();
        Set<Character> set=new HashSet<>();
        for(Character c : s.toCharArray()) {
     
            map.put(c, map.getOrDefault(c, 0) + 1);
           // System.out.println(c+":"+map.get(c));

        }
        for(Character c : s.toCharArray() )
        //for (int i=0 ; i
        {
     
           // Character c = s.charAt(i);
            if (!set.contains(c))
            {
     
                //          ,          peek  
                //        stack                    ，             
                //              ，         
                while ( !stack.isEmpty() && stack.peek() > c && map.get(stack.peek()) >= 1)
                {
     
                //             
                    set.remove(stack.peek());
                    stack.pop();
                }
                stack.push(c);
                set.add(c);
            }
            //   ，            map      1  
            map.put(c,map.get(c)-1);
            
        }
        //     stringbuilder stringbuffer   
        //  String      ，StringBuffer   StringBuilder             ，            。
         // StringBuilder    Java 5     ，
        //   StringBuffer           StringBuilder           （      ）。
//   StringBuilder     StringBuffer      ，            StringBuilder  。
//                 ，      StringBuffer  。
        StringBuilder stringBuilder=new StringBuilder();
        while ( !stack.isEmpty() ) stringBuilder.append(stack.pop());
        stringBuilder.reverse();
        return stringBuilder.toString();
    }