최용기 (최대 대기 열, 최소 스 택) 템 플 릿

때때로 제목 이 주 는 입력 은 일부 용기 의 특성 을 만족 시 킵 니 다. 예 를 들 어 미끄럼 창 = 대기 열, FIFO = 스 택 등 이 있 습 니 다. 그러면 가장 값 을 요구 하 는 동시에 정상 용기 의 pop, top 작업 도 실현 해 야 합 니 다. 그러면 이 템 플 릿 을 고려 할 수 있 습 니 다.
사실 관건 은:

정상 용기 와 보조 용 기 를 사용 합 니 다. 두 용기 의 삽입 삭제 단 은 일치 해 야 합 니 다 (예 를 들 어 push back (), pop front ()

데 이 터 를 읽 고 정상 용기 가 정상적으로 삽입 되 며 삭제

보조 용 기 는 유지 해 야 합 니 다. 1. 읽 기 단 에서 유지 하 는 것 이 가장 값 이 어야 합 니 다. 2. 삽입 단 에서 질 서 를 유지 하고 유지 하 는 성질 1. 즉, 삽입 단 요소 와 새로운 요소 의 크기 를 계속 비교 하여 삽입 단 이 pop / push 인지 여 부 를 결정 합 니 다. 읽 기 단 이 경 계 를 넘 지 않 습 니 다. 정상 적 인 용기 가 삭제 되면 보조 용기 의 읽 기 단 은 삭제 할 요소 입 니 다.그러면 보조 용기 읽 기 단 pop

용 기 를 정상적으로 읽 습 니 다. 정상 용기 의 읽 기 단 을 참고 하여 가장 값 진 요 소 를 읽 으 려 면 보조 용기 의 읽 기 단 을 참고 하 십시오.
가장 작은 창고
push, pop, top 작업 을 지원 하고 상수 시간 내 에 최소 요 소 를 검색 할 수 있 는 스 택 을 설계 합 니 다.
push (x) – 원소 x 를 창고 에 밀어 넣 습 니 다.pop () – 스 택 상단 의 요 소 를 삭제 합 니 다.top () – 스 택 상단 요 소 를 가 져 옵 니 다.getMin () - 검색 창고 의 최소 요소 입 니 다.
예시:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   -->    -3.
minStack.pop();
minStack.top();      -->    0.
minStack.getMin();   -->    -2.

출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/min-stack 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.

class MinStack {
public:
    /** initialize your data structure here. */
    deque<int> s;		//   
    deque<int> mins;	//   
    MinStack() {

    }
    
    void push(int x) {
        s.push_back(x);
        //        ，     =   ，                  
        if(mins.empty() || mins.back()>=x) mins.push_back(x);
    }
    
    void pop() {
    	//         ，      pop ，            
        if(mins.back()==s.back()) mins.pop_back();
        s.pop_back();
    }
    
    int top() {
        return s.back();
    }
    
    int getMin() {
        return mins.back();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

면접 문제 59 - II. 대열 의 최대 치
하나의 대기 열 을 정의 하고 함수 max 를 실현 하 십시오.value 대기 열 에서 최대 값 을 얻 습 니 다. 함수 max 요구value、push_back 과 popfront 의 시간 복잡 도 는 모두 O (1) 이다.
대기 열 이 비어 있 으 면, popfront 와 maxvalue 되 돌려 줘 야 돼 - 1
예제 1: 입력: ["MaxQueue", "push back", "push back", "max value", "pop front", "max value"] [[], [1], [2], [], [], [], []] 출력: [null, null, null, 2, 1, 2]
예제 2: 입력: ["MaxQueue", "pop front", "max value"] [[], [], []] 출력: [null, - 1, - 1]
제한: 1 < = pushback,pop_front,max_value 의 총 조작 수 < = 10000 1 < = value < = 10 ^ 5
[제목 전송 문]
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.

class MaxQueue {
public:
    deque<int> q;
    deque<int> maxq;
    MaxQueue() {

    }
    
    int max_value() {
        if(maxq.empty()) return -1;
        return maxq.front();
    }
    
    void push_back(int value) {
        q.push_back(value);
        //         ：       ，          
        while(!maxq.empty() && maxq.back()<=value) maxq.pop_back();
        maxq.push_back(value);
    }
    
    int pop_front() {
        if(q.empty()) return -1;
        int f=q.front(); q.pop_front();
        //         ：               ，    
        if(maxq.front()==f) maxq.pop_front();
        return f;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */