Min Stack Leetcode โซลูชัน


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน แอปเปิล บลูมเบิร์ก ทุนหนึ่ง ไมโครซอฟท์ คำพยากรณ์
ออกแบบ กอง

คำชี้แจงปัญหา

ออกแบบก กอง ที่รองรับการผลักดันป๊อปด้านบนและการดึงองค์ประกอบขั้นต่ำในเวลาคงที่

push (x) - ผลักองค์ประกอบ x ไปยังสแต็ก
pop () - ลบองค์ประกอบที่ด้านบนของสแต็ก
top () - รับองค์ประกอบด้านบน
getMin () - ดึงองค์ประกอบขั้นต่ำในสแต็ก

หมายเหตุ: การดำเนินการเมธอด pop, top และ getMin จะถูกเรียกใช้บนสแต็กที่ไม่ว่างเปล่าเสมอ

ตัวอย่าง

push(-2);
push(0);
push(-3);
getMin();
pop();
top();
getMin();
-3
0
-2

คำอธิบาย:

MinStack minStack = MinStack ใหม่ ();
minStack.push (-2);
minStack.push (0);
minStack.push (-3);
minStack.getMin (); // กลับ -3
minStack.pop ();
minStack.top (); // กลับ 0
minStack.getMin (); // กลับ -2

เข้าใกล้

เราทราบดีว่าสแต็กเป็นโครงสร้างข้อมูลที่เราสามารถพุชองค์ประกอบในตอนท้ายได้อย่างง่ายดายและยังเข้าถึงหรือเปิดองค์ประกอบที่แทรกสุดท้ายได้อย่างง่ายดาย การดำเนินการเหล่านี้เกิดขึ้นใน O (1) ครั้งในสแต็ก แต่ในปัญหานี้เราต้องสร้างฟังก์ชันพิเศษ getMin ที่ควรจะสามารถเรียกคืนองค์ประกอบขั้นต่ำในสแต็กและในเวลา O (1)

ดังนั้นในการออกแบบโครงสร้างข้อมูลนี้เราจะใช้สแต็กเป็นโครงสร้างข้อมูลหลักอย่างเห็นได้ชัด แต่เราต้องเพิ่มอัลกอริทึมพิเศษเข้าไปเพื่อให้เราได้รับองค์ประกอบขั้นต่ำในเวลาคงที่

สำหรับสิ่งนี้ให้ดูตัวอย่าง สมมติว่าเราต้องแทรกองค์ประกอบเหล่านี้ตามลำดับ:
5 6 4 7 5 3 แล้วเริ่ม popping

Min Stack Leetcode โซลูชัน

เราสามารถสังเกตได้ว่าเมื่อเราเปิดองค์ประกอบซึ่งเป็นค่าต่ำสุดในปัจจุบันด้วยแล้วค่าต่ำสุดใหม่จะเหมือนกับตอนก่อนที่จะผลักดันมัน ดังนั้นเราจึงต้องมีความรู้เกี่ยวกับองค์ประกอบขั้นต่ำก่อนหน้าทั้งหมดจนถึงตอนนี้เพื่อที่เราจะได้รับค่าต่ำสุดหลังจากลบองค์ประกอบขั้นต่ำปัจจุบันในเวลา O (1)

สำหรับสิ่งนี้เราสามารถใช้สแต็กอื่นซึ่งจะเก็บเฉพาะองค์ประกอบขั้นต่ำ (แสดงด้วยสีเขียวในรูป) ของสแต็กหลัก ดังนั้นองค์ประกอบบนสุดของสแต็กขั้นต่ำจะบอกองค์ประกอบขั้นต่ำในปัจจุบัน

ในระหว่างการแทรกหรือลบองค์ประกอบเราจะอัปเดต min stack ดังต่อไปนี้:

  • หากองค์ประกอบที่พุชใหม่มีค่าน้อยกว่าหรือเท่ากับค่าต่ำสุดในปัจจุบันเราจะพุชองค์ประกอบนี้ลงในสแต็กขั้นต่ำด้วยเพื่ออัปเดตค่าต่ำสุดปัจจุบัน
  • หากองค์ประกอบ popped เท่ากับค่าต่ำสุดในปัจจุบันเราจะลบองค์ประกอบนี้ออกจากสแต็กขั้นต่ำด้วยเพื่ออัปเดตขั้นต่ำปัจจุบัน

การดำเนินงาน

โปรแกรม C ++ สำหรับ Min Stack Leetcode Solution

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

class MinStack {
public:
    stack<int> st,mn;
    
    void push(int x) 
    {
        if(st.empty() || x<=mn.top())
            mn.push(x);
        st.push(x);
    }
    
    void pop() 
    {
        if(st.top()==mn.top()) 
            mn.pop();
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return mn.top();
    }
};

int main() 
{
    MinStack* minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    int param1 = minStack->getMin(); 
    minStack->pop();
    int param2 = minStack->top();   
    int param3 = minStack->getMin(); 
    
    cout<<param1<<endl;
    cout<<param2<<endl;
    cout<<param3<<endl;
    
    return 0; 
}
-3
0
-2

โปรแกรม Java สำหรับ Min Stack Leetcode Solution

import java.util.*;
class MinStack {

    Stack<Integer> st=new Stack<>();
    Stack<Integer> mn=new Stack<>();
   
    public void push(int x) 
    {
        if(st.empty() || x<=mn.peek())
            mn.push(x);
        st.push(x);
    }
    
    public void pop() 
    {
        if(st.peek().equals(mn.peek())) 
            mn.pop();
        st.pop();
    }
    
    public int top() 
    {
         return st.peek();
    }
    
    public int getMin() 
    {
        return mn.peek();
    }
}

class Rextester{

  public static void main(String args[])
    {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int param1 = minStack.getMin(); 
        minStack.pop();
        int param2 = minStack.top();   
        int param3 = minStack.getMin(); 
        
    System.out.println(param1);
        System.out.println(param2);
        System.out.println(param3);
    }
}
-3
0
-2

การวิเคราะห์ความซับซ้อนสำหรับ Min Stack Leetcode Solution

ความซับซ้อนของเวลา

O (1): O (1) สำหรับการดำเนินการทั้งหมด ดังที่เราทราบดีว่าสแต็กใช้เวลาคงที่ในการพุชป๊อปและด้านบน สำหรับ getMin เราได้ใช้สแต็กอื่นซึ่งทำให้ฟังก์ชันนี้ทำงานในเวลาคงที่

ความซับซ้อนของอวกาศ 

บน) : ในกรณีที่เลวร้ายที่สุดการดำเนินการทั้งหมดถูกผลักดันดังนั้นความซับซ้อนของพื้นที่จึงเป็น O (n)