设计一个支持O(1)时间和O(1)额外空间的getMin()的堆栈  


难度级别 易得奖学金
经常问 土砖 亚马逊 事实集 Flipkart 高盛 GreyOrange 库利扎 微软 Paytm 阳狮精明 树液 Snapdeal VMware的

设计一个支持O(1)时间和O(1)额外空间的getMin()的堆栈。 因此,特殊 数据结构必须支持堆栈的所有操作,例如–

  • 无效push()
  • int pop()
  • 布尔isFull()
  • bool isEmpty()

在恒定的时间内。 添加一个额外的操作getMin()以在恒定时间内返回特殊堆栈中的最小值,并增加O(1)额外空间。

设计一个支持O(1)时间和O(1)额外空间的getMin()的堆栈Pin

使用案列  

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是否小于最小打印分钟数,并将最小更新为2 * min – t。
  8. 其他打印t。
  9. 创建函数getMin()并检查堆栈是否为空,打印“ Stack is empty”。
  10. 否则返回最小元素。

代码  

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) 因为我们正在使用竞争性辅助空间。 存储输入所需的空间不计入算法的空间复杂度。