검 지 offer (22): min 함 수 를 포함 하 는 창고
3070 단어 검지 제공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에 따라 라이센스가 부여됩니다.