Նախագծեք մի բուրգ, որն աջակցում է getMin () - ին O (1) ժամանակում և O (1) լրացուցիչ տարածության մեջ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon Փաստեր Flipkart Goldman Sachs-ը GreyOrange Կուլիզա Microsoft Paytm Publicis Sapient SAP Snapdeal VMware
Գրապահոց

Նախագծեք մի բուրգ, որն աջակցում է getMin () - ին O (1) ժամանակում և O (1) լրացուցիչ տարածության մեջ: Այսպիսով, հատուկ բուրգ տվյալների կառուցվածքը պետք է աջակցի բուրգի բոլոր գործողություններին ՝

  • անվավեր հրել ()
  • int pop ()
  • bool isFull ()
  • bool is դատարկ ()

մշտական ​​ժամանակում: Ավելացրեք լրացուցիչ գործողություն getMin () ՝ ստեկի ժամանակ նվազագույն արժեքը վերադարձնելու համար հաստատուն ժամանակում և O (1) լրացուցիչ տարածք:

Նախագծեք մի բուրգ, որն աջակցում է getMin () - ին O (1) ժամանակում և O (1) լրացուցիչ տարածության մեջ

Օրինակ

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. Նախաձեռնեք մի կառույց newStack- ը և ստեղծել գործառույթ մղել () դրանում, որն ամբողջ թիվն ընդունում է որպես պարամետր:
  2. Ստուգեք, թե դեղը դատարկ է, պահեք այն ամբողջ թիվ փոփոխական րոպեում, ամբողջ թիվը տեղադրեք բուրգում և վերադարձեք:
  3. Ուրիշ, եթե ամբողջ թիվը min- ից պակաս է, ներդիր 2 * x - րոպե տուփի մեջ և թարմացրու min- ը x- ով:
  4. Ուրիշը ամբողջությամբ մղեք բուրգով:
  5. Ստեղծեք pop () գործառույթը: Ստուգեք, թե դեղը դատարկ է. «Դուրը դատարկ է» տպեք և վերադարձեք:
  6. Այլապես պահեք տարրը դեղի վերևում t փոփոխականում և վերևից հանեք վերից:
  7. Ստուգեք, արդյոք t- ը րոպեից պակաս է տպման րոպեից և թարմացրեք min- ը որպես 2 * min - t:
  8. Այլ տպել t.
  9. Ստեղծեք getMin () գործառույթը և ստուգեք, թե արդյոք դեղը դատարկ է: «Դուրը դատարկ է» տպեք:
  10. Այլապես վերադարձեք նվազագույն տարրը:

Կոդ

C ++ ծրագիր minStack- ի համար

#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

Java ծրագիր minStack- ի համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

Ո (1) յուրաքանչյուր գործողության համար, քանի որ բոլոր գործողությունները կատարվում են մշտական ​​ժամանակում:

Տիեզերական բարդություն

Ո (1) քանի որ մենք օգտագործում ենք կոնտենտային օժանդակ տարածք: Ներածումը պահելու համար անհրաժեշտ տարածությունը չի հաշվարկվում ալգորիթմի տարածական բարդության համար: