O (1) 시간 및 O (1) 추가 공간에서 getMin ()을 지원하는 스택 설계

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 팩트 셋 Flipkart 골드만 삭스 그레이 오렌지 쿨리 자 Microsoft Paytm 퍼블리 시스 사피엔 트 SAP 스냅 딜 VM웨어
스택조회수 58

O (1) 시간 및 O (1) 추가 공간에서 getMin ()을 지원하는 스택을 설계합니다. 따라서 특별 스택 데이터 구조는 다음과 같은 스택의 모든 작업을 지원해야합니다.

  • 무효 push ()
  • int pop ()
  • bool isFull ()
  • bool isEmpty ()

일정한 시간에. 추가 연산 getMin ()을 추가하여 일정한 시간과 O (1) 추가 공간에서 특수 스택의 최소값을 반환합니다.

O (1) 시간 및 O (1) 추가 공간에서 getMin ()을 지원하는 스택 설계

push(30)
push(20)
push(10)
getMin()
pop()
getMin()
Minimum element : 10
Popped element : 10
Minimum element : 20
push(500)
push(50)
push(5)
getMin()
pop()
getMin()
Minimum element : 5
Popped element : 5
Minimum element : 50

minStack을 구현하기위한 수학적 / 관찰 된 방법

이 접근 방식에서는 최소 요소를 다음과 같이 업데이트합니다.

push () 함수에서 푸시 할 정수가 최소 요소보다 작 으면 해당 정수의 두 배에서 최소 요소를 뺀 스택에 삽입합니다.이 요소는 항상 주어진 정수보다 작습니다.

  • 주어진 정수 <주어진 정수를 의미하는 최소 요소 – 최소 요소 <0
  • // 양쪽에 주어진 정수 추가
  • 주어진 정수 – 최소 요소 + 주어진 정수 <0 + 주어진 정수
  • 2 * 주어진 정수 – 최소 요소 <주어진 정수
  • 2 * 주어진 정수 – 최소 요소 <새로운 최소 요소

따라서이 요소를 튀어 나오는 동안 최소 요소보다 작으므로 최소 요소를 업데이트합니다.

마찬가지로 pop () 함수에서 현재 요소가 최소 요소보다 작 으면 업데이트합니다.

암호알고리즘

  1. 구조 초기화 뉴스택 함수를 만듭니다. 푸시() 정수를 매개 변수로 받아들이는 그 안에.
  2. 스택이 비어 있는지 확인하고 정수 min 변수에서 스택에 정수를 삽입하고 반환합니다.
  3. 정수가 min보다 작 으면 2 * x – min을 스택에 삽입하고 min을 x로 업데이트합니다.
  4. 그렇지 않으면 스택의 정수를 푸시하십시오.
  5. pop () 함수를 만듭니다. 스택이 비어 있는지 확인하고“스택이 비어 있음”을 인쇄하고 반환합니다.
  6. 그렇지 않으면 변수 t의 스택 맨 위에 요소를 저장하고 스택에서 맨 위 요소를 팝 / 제거합니다.
  7. t가 min print min보다 작은 지 확인하고 min을 2 * min – t로 업데이트하십시오.
  8. 그렇지 않으면 t.
  9. getMin () 함수를 생성하고 스택이 비어 있는지 확인하십시오. "Stack is empty"를 인쇄하십시오.
  10. Else는 최소 요소를 반환합니다.

암호

minStack 용 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
struct newStack{ 
    stack<int> s; 
    int min; 
  
    void getMin(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
        }
        else{
            cout<<"Minimum element : "<<min<<"\n"; 
        }    
    } 
  
    void pop(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
            return; 
        } 
  
        cout<<"Popped element : "; 
        int t = s.top(); 
        s.pop(); 
  
        if(t<min){ 
            cout<<min<< "\n"; 
            min = 2*min - t; 
        } 
  
        else{
            cout<<t<< "\n";
        }    
    } 
  
    void push(int x){ 
        if(s.empty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x < min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
           s.push(x);
        }   
    } 
}; 
 
int main(){
    newStack s; 
    
    s.push(30);
    s.push(20);
    s.push(10);
    s.getMin();
    s.pop();
    s.getMin();
  
    return 0; 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

minStack 용 Java 프로그램

import java.util.*; 
  
class newStack{ 
    Stack<Integer> s; 
    Integer min; 
  
    newStack(){ 
        s = new Stack<Integer>(); 
    } 
  
    void getMin(){ 
        if(s.isEmpty()) 
            System.out.println("Stack is empty"); 
  
        else{
            System.out.println("Minimum element : " + min);
        }    
    } 
  
    void pop(){ 
        if (s.isEmpty()){ 
            System.out.println("Stack is empty"); 
            return; 
        } 
  
        System.out.print("Popped element : "); 
        Integer t = s.pop(); 
  
        if(t<min){ 
            System.out.println(min); 
            min = 2*min - t; 
        } 
  
        else{
            System.out.println(t);
        }    
    } 
  
    void push(Integer x){ 
        if(s.isEmpty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x<min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
            s.push(x); 
        }    
    } 
}; 
  
public class Main{ 
    public static void main(String[] args){ 
        newStack s = new newStack(); 
        
        s.push(30);
        s.push(20);
        s.push(10);
        s.getMin();
        s.pop();
        s.getMin();
        
    } 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

복잡성 분석

시간 복잡성

O (1) 모든 작업이 일정한 시간에 수행되므로 각 작업에 대해.

공간 복잡성

O (1) 일정한 보조 공간을 사용하고 있기 때문입니다. 입력을 저장하는 데 필요한 공간은 알고리즘의 공간 복잡성에 포함되지 않습니다.

Translate »