검 지 offer (22): min 함 수 를 포함 하 는 창고

제목 설명
스 택 의 데이터 구 조 를 정의 합 니 다. 이 형식 에서 스 택 의 최소 요 소 를 얻 을 수 있 는 min 함 수 를 실현 하 십시오.이 스 택 에서 min, push, pop 을 호출 하 는 시간 복잡 도 는 모두 O (1) 입 니 다.
분석 하 다.
가장 직접적인 사고: 매번 에 하나의 요소 가 스 택 에 들 어 갈 때마다 정렬 을 하고 가장 작은 요 소 를 스 택 꼭대기 에 있 게 하 며 O (1) 시간 안에 가장 작은 요 소 를 찾 을 수 있 습 니 다.그러나 이 방법 은 '선진 후 출' 창고 의 특성 을 보장 할 수 없다.
추천 해법: 보조 스 택 mins 를 사용 하여 스 택 에 들 어 갈 때마다 작업 하 는 최소 요 소 를 저장 합 니 다. min () 함 수 는 보조 스 택 mins 의 스 택 꼭대기 에서 팝 업 작업 을 하고 O (1) 시간 안에 완성 하여 공간 으로 시간 을 바 꿉 니 다.최소 요소 가 원 데이터 스 택 data 에서 팝 업 되 었 을 때 보조 스 택 mins 내 스 택 요 소 를 팝 업 하면 mins 보조 스 택 의 새로운 스 택 요 소 는 다음 최소 값 입 니 다.
우 객 AC 코드:
/** *         ,                    min  。 *       ,  min push pop        O(1) */

import java.util.Stack;

public class MinStack {

    Stack<Integer> data = new Stack<Integer>(); //    
    Stack<Integer> mins = new Stack<Integer>(); //    ,     
    Integer tmpMin = null;

    //     ,     
    public void push(int node) {
        if(tmpMin == null) {
            tmpMin = node;
            data.push(node);
            mins.push(node);
        } else {
            if(node <= tmpMin) {
                tmpMin = node;
                mins.push(node);
            }
            data.push(node);
        }
    }

    //       
    public void pop() {
        int num1 = data.pop();
        int num2 = mins.pop();
        if(num1 != num2)
            mins.push(num2);
    }

    //       
    public int top() {
        int num = data.pop();
        data.push(num);
        return num;
    }

    //         
    public int min() {
        int num = mins.pop();
        mins.push(num);
        return num;
    }
}

참고 1. 하 해도, 검 지 는 유명 기업 면접 관 에 게 전형 적 인 프로 그래 밍 문제 (기념 판), 전자 공업 출판사

좋은 웹페이지 즐겨찾기