ການແກ້ໄຂ Leetcode ຂັ້ນຕ່ ຳ ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Bloomberg Capital One Microsoft Oracle
ການອອກແບບ Stack

ຖະແຫຼງການບັນຫາ

ອອກແບບກ stack ທີ່ສະ ໜັບ ສະ ໜູນ ການຊຸກຍູ້, ປpopອບອັບ, ດ້ານເທິງ, ແລະການດຶງເອົາອົງປະກອບຕ່ ຳ ສຸດໃນເວລາຄົງທີ່.

ຍູ້ (x) - ຍູ້ອົງປະກອບ x ລົງສູ່ຂັ້ນໄດ.
pop () - ເອົາສ່ວນປະກອບອອກມາເທິງຊັ້ນວາງ.
top () - ໄດ້ຮັບອົງປະກອບອັນດັບ ໜຶ່ງ.
getMin () - ດຶງເອົາອົງປະກອບຕ່ ຳ ສຸດໃນ stack.

ໝາຍ ເຫດ: ວິທີການ ດຳ ເນີນງານແບບ 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

ວິທີການ

ພວກເຮົາຮູ້ວ່າ stack ແມ່ນໂຄງສ້າງຂໍ້ມູນທີ່ພວກເຮົາສາມາດຍູ້ອົງປະກອບໃດ ໜຶ່ງ ໃນຕອນສຸດທ້າຍໄດ້ງ່າຍແລະຍັງສາມາດເຂົ້າເຖິງຫລືເລືອກເອົາອົງປະກອບທີ່ຖືກໃສ່ມາລ້າສຸດ. ການປະຕິບັດງານເຫຼົ່ານີ້ເກີດຂື້ນໃນເວລາ O (1) ໃນ stack. ແຕ່ໃນບັນຫານີ້ພວກເຮົາຕ້ອງໄດ້ເຮັດ ໜ້າ ທີ່ເພີ່ມເຕີມ getMin ທີ່ຄວນຈະສາມາດດຶງເອົາອົງປະກອບຂັ້ນຕ່ ຳ ໃນຊັ້ນແລະໃນເວລາ O (1).

ສະນັ້ນເພື່ອອອກແບບໂຄງສ້າງຂໍ້ມູນນີ້ແນ່ນອນພວກເຮົາຈະໃຊ້ stack ເປັນໂຄງສ້າງຂໍ້ມູນຫຼັກແຕ່ພວກເຮົາຕ້ອງໄດ້ຕື່ມຂັ້ນຕອນພິເສດບາງຢ່າງໃຫ້ມັນເພື່ອພວກເຮົາຈະສາມາດໄດ້ຮັບສ່ວນປະກອບຂັ້ນຕ່ ຳ ໃນເວລາຄົງທີ່.

ສຳ ລັບສິ່ງນີ້, ໃຫ້ເບິ່ງຕົວຢ່າງ. ຂໍໃຫ້ສົມມຸດວ່າພວກເຮົາຕ້ອງໃສ່ບັນດາອົງປະກອບເຫຼົ່ານີ້ເຂົ້າໃນ ລຳ ດັບ:
5 6 4 7 5 3, ແລະຫຼັງຈາກນັ້ນເລີ່ມຕົ້ນ popping.

ການແກ້ໄຂ Leetcode ຂັ້ນຕ່ ຳ ສຸດ

ພວກເຮົາສາມາດສັງເກດເຫັນວ່າເມື່ອພວກເຮົາປ້ອນອົງປະກອບທີ່ຍັງ ຕຳ ່ສຸດໃນປະຈຸບັນນີ້ແລ້ວ ຕຳ ່ສຸດທີ່ ໃໝ່ ແມ່ນຄືກັນກັບໃນຂະນະທີ່ກ່ອນທີ່ຈະຍູ້ມັນ. ສະນັ້ນພວກເຮົາຕ້ອງມີຄວາມຮູ້ກ່ຽວກັບທຸກໆອົງປະກອບ ຕຳ ່ສຸດທີ່ກ່ອນ ໜ້າ ນີ້ຈົນເຖິງປະຈຸບັນພວກເຮົາສາມາດດຶງເອົາ ຕຳ ່ສຸດທີ່ໄດ້ຫຼັງຈາກ ກຳ ຈັດອົງປະກອບ ຕຳ ່ສຸດໃນປະຈຸບັນໃນເວລາ O (1).

ສຳ ລັບສິ່ງນີ້ພວກເຮົາສາມາດ ນຳ ໃຊ້ stack ອີກອັນ ໜຶ່ງ ເຊິ່ງຈະເກັບຮັກສາພຽງແຕ່ສ່ວນປະກອບຕ່ ຳ ສຸດ (ທີ່ສະແດງດ້ວຍສີຂຽວໃນຮູບ) ຂອງ stack ຕົ້ນຕໍ. ດັ່ງນັ້ນອົງປະກອບຊັ້ນສູງສຸດຂອງຂັ້ນຕ່ ຳ ສຸດຈະບອກອົງປະກອບຕ່ ຳ ສຸດໃນປະຈຸບັນ.

ໃນລະຫວ່າງການແຊກຫຼື ກຳ ຈັດອົງປະກອບໃດ ໜຶ່ງ ພວກເຮົາຈະປັບປຸງ min stack ດັ່ງລຸ່ມນີ້:

  • ຖ້າຫາກວ່າອົງປະກອບທີ່ຖືກຊຸກດັນ ໃໝ່ ມີ ໜ້ອຍ ກວ່າຫຼືເທົ່າກັບ ຕຳ ່ສຸດທີ່ປັດຈຸບັນນີ້ພວກເຮົາຍູ້ອົງປະກອບນີ້ອອກເປັນ min stack ກໍ່ເພື່ອປັບປຸງ ຕຳ ່ສຸດທີ່ປະຈຸບັນ.
  • ຖ້າວ່າອົງປະກອບທີ່ເກີດຂື້ນມາເທົ່າກັບ ຕຳ ່ສຸດທີ່ປະຈຸບັນຫຼັງຈາກນັ້ນພວກເຮົາຈະເອົາອົງປະກອບນີ້ອອກຈາກ min stack ກໍ່ເພື່ອປັບປຸງ ຕຳ ່ສຸດທີ່ປະຈຸບັນ.

ການປະຕິບັດ

ໂປຣແກຣມ 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 Program ສຳ ລັບ 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) ສຳ ລັບທຸກໆການ ດຳ ເນີນງານ. ດັ່ງທີ່ພວກເຮົາຮູ້ວ່າ stack ໃຊ້ເວລາຄົງທີ່ ສຳ ລັບການຊຸກຍູ້, ປpopອບອັບ, ແລະດ້ານເທິງ. ສຳ ລັບ getMin ພວກເຮົາໄດ້ໃຊ້ stack ອີກອັນ ໜຶ່ງ ທີ່ເຮັດໃຫ້ຟັງຊັນນີ້ຍັງໃຊ້ງານໄດ້ຕະຫຼອດເວລາ.

ຄວາມສັບສົນໃນອະວະກາດ 

ໂອ (n): ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດການ ດຳ ເນີນງານທັງ ໝົດ ແມ່ນການຊຸກຍູ້, ເພາະສະນັ້ນຄວາມສັບສົນທາງດ້ານພື້ນທີ່ແມ່ນ O (n).