최소 스택


난이도 쉽게
자주 묻는 질문 아마존 블룸버그 자본 하나 DBOI 도이치 은행 골드만 삭스 구글 Microsoft 신탁 월마트 연구소
디자인 스택

최소 스택 문제에서 우리는 스택 다음 기능을 효율적으로 구현하기 위해
푸시 (x) –> 요소 x를 스택으로 푸시
팝() –> 스택 맨 위에있는 항목을 제거합니다.
상단() –> 스택 맨 위에있는 요소를 반환합니다.
getMin () –> 스택에있는 최소 요소를 반환합니다.

입력:
푸시 -2
푸시 0
최소 가져 오기
푸시 -3

상의
최소 가져 오기
출력:
-2
0
-2

최소 스택에 대한 알고리즘

push, pop 및 top 메서드는 일반 스택과 유사하지만 스택에있는 최소 요소를 가져 오기 위해 모든 요소까지 최소값을 저장하는 스택을 하나 더 사용합니다.

첫 번째 스택을 st, 두 번째 스택을 minSt로 설정 한 다음

푸시 (x)

  1. x를 스택 st에 밀어 넣습니다.
  2. minSt가 비어 있거나 minSt의 상단이 x보다 크면 x를 minSt로 누릅니다.
  3. 그렇지 않으면 minSt의 상단을 minSt로 다시 밉니다.

시간 복잡성 =O (1) 
공간 복잡성 =O (1)

팝()

스택 st 및 스택 minSt에서 요소를 팝합니다.

시간 복잡성 =O (1) 
공간 복잡성 =O (1)

상단()

스택의 맨 위를 반환합니다.

시간 복잡성 =O (1) 
공간 복잡성 =O (1)

getMin ()

스택 minSt의 맨 위를 반환합니다.

시간 복잡성 =O (1) 
공간 복잡성 =O (1)

전반적인 공간 복잡성 = O (n) 
여기서 n은 한 번에 스택으로 푸시되는 최대 요소 수입니다.

최소 스택에 대한 설명

위의 예를 고려하십시오.
두 스택 st 및 minSt를 초기화합니다.
st = null 및 minSt = null

  1. 푸시 (-2)
    st = (-2) 및 minSt = (-2)
  2. 푸시 0
    st = 0-> (-2) 및 minSt = (-2)-> (-2)
  3. getMin
    Top of minSt = (-2), return (-2)
  4. 푸시 (-3)
    st = (-3)-> 0-> (-2) 및 minSt = (-3)-> (-2)-> (-2)

  5. st = 0-> (-2) 및 minSt = (-2)-> (-2)
  6. 상의
    스택의 맨 위 st는 0이고 0을 반환합니다.
  7. getMin
    스택의 최상위 minSt는 (-2)이고 (-2)를 반환합니다.

자세한 내용은 아래 이미지를 참조하십시오.

최소 스택

최소 스택 용 JAVA 코드

import java.util.Stack;

public class MinStack {
    private static Stack<Integer> st;
    private static Stack<Integer> minSt;

    private static void push(int x) {
        // Push x to stack st
        st.push(x);
        // If minSt is empty or if top of minSt is greater than x push x to minSt.
        if (minSt.isEmpty() || minSt.peek() > x) {
            minSt.push(x);
        } else {
            // Else push top of minSt to minSt again.
            minSt.push(minSt.peek());
        }
    }

    private static void pop() {
        // Pop element from st and minSt
        st.pop();
        minSt.pop();
    }
    
    private static int top() {
        // Return top of st
        return st.peek();
    }
    
    private static int getMin() {
        // Return top of minSt
        return minSt.peek();
    }

    public static void main(String[] args) {
        // Initialise st and minSt
        st = new Stack<>();
        minSt = new Stack<>();

        // Example
        push(-2);
        push(0);
        System.out.println(getMin());
        push(-3);
        pop();
        System.out.println(top());
        System.out.println(getMin());
    }
}
-2
0
-2

최소 스택 용 C ++ 코드

#include<bits/stdc++.h> 
using namespace std;

stack<int> st;
stack<int> minSt;

void push(int x) {
    // Push x to stack st
    st.push(x);
    // If minSt is empty or if top of minSt is greater than x push x to minSt.
    if (minSt.empty() || minSt.top() > x) {
        minSt.push(x);
    } else {
        // Else push top of minSt to minSt again.
        minSt.push(minSt.top());
    }
}

void pop() {
    // Pop element from st and minSt
    st.pop();
    minSt.pop();
}

int top() {
    // Return top of st
    return st.top();
}

int getMin() {
    // Return top of minSt
    return minSt.top();
}

int main() {
    // Example
    push(-2);
    push(0);
    cout<<getMin()<<endl;
    push(-3);
    pop();
    cout<<top()<<endl;
    cout<<getMin()<<endl;
    
    return 0;
}
-2
0
-2

참조