검 지 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. 하 해도, 검 지 는 유명 기업 면접 관 에 게 전형 적 인 프로 그래 밍 문제 (기념 판), 전자 공업 출판사

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

\ # 데이터 구조 와 알고리즘 학습 노트 \ # 검 지 제공 42: 단어 순 서 를 뒤 집기 + 테스트 사례 (자바, C / C +)

2019.1.2 검 지 Offer 는 제로 브러시 개인 노트 정리 (66 문제 전) 디 렉 터 리 전송 문 에서 인터넷 에 서 는 원 서 를 포함 한 많은 방법 이 문장 을 두 번 뒤 집 는 것 이다. 첫 번...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

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

좋은 웹페이지 즐겨찾기