स्टैक मिन: पुश, पॉप और मिन() ओ(१) में (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ३.२: ऐसा स्टैक डिज़ाइन करो जो मौजूदा न्यूनतम अचर समय में लौटाए। दूसरी स्टैक से मिन ट्रैक करो (या हर नोड पर अब-तक-का-मिन), साफ जावा में।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम स्कोर की चिप्पियाँ एक कप में रखते हो। हमेशा ऊपर ही डालते हो या ऊपर वाली ही निकालते हो। कभी दोस्त पूछता है, "कप में अभी सबसे कम स्कोर क्या है?" अगर सब बाहर निकालकर देखो तो धीमा है। अगर एक छोटा दूसरा कप रखो जिसमें सिर्फ नए निम्न अंक आते हों, तो एक झलक में जवाब मिल जाता है। वही दूसरा कप स्टैक मिन का विचार है।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली स्टैक-समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ३, स्टैक और कतार।

१. रोज़मर्रा की उपमा

सामान्य स्टैक प्लेटों का ढेर है: जो आखिर में रखा, वही पहले निकलेगा। हमेशा ऊपर की प्लेट दिखती है। नीचे दबी सबसे सस्ती प्लेट अपने आप नहीं पता चलती।

स्टैक मिन एक नियम जोड़ता है: किसी भी पल तुम्हें पता होना चाहिए कि स्टैक में अभी सबसे छोटा मान क्या है, बिना पूरी लिस्ट घूमे।

पुश(x): x ऊपर रखो।
पॉप(): ऊपर वाला हटाओ।
मिन(): अभी स्टैक में बचे सभी मानों में से सबसे छोटा लौटाओ। स्टैक गहरा हो तो भी तेज़ रहना चाहिए।

चाल चालाक खोज नहीं है। चाल है पुश करते समय नए निम्न का इतिहास याद रखना, और किसी निम्न को तभी भूलना जब उसी मान का पॉप हो जो उसे बनाता था।

२. समस्या सादे शब्दों में

बनाओ पूर्णांकों का स्टैक तीन संक्रियाओं के साथ, हर एक ओ(१) समय में:

संक्रिया	अर्थ
`push(value)`	स्टैक पर धकेलो
`pop()`	ऊपर वाला हटाकर लौटाओ
`min()`	अभी स्टैक में सबसे छोटा मान लौटाओ (हटाओ मत)

वैकल्पिक मदद: peek(), isEmpty()। वही जटिलता लक्ष्य।

उदाहरण:

क्रिया	स्टैक (तल → ऊपर)	मिन()
पुश ५	५	५
पुश ३	५, ३	३
पुश ७	५, ३, ७	३
पुश ३	५, ३, ७, ३	३
पॉप	५, ३, ७	३
पॉप	५, ३	३
पॉप	५	५

कोड से पहले साफ करो:

इस लेख में सिर्फ पूर्णांक? (हाँ। कोई भी तुलनीय प्रकार पर वही पैटर्न चलता है।)
खाली स्टैक पर min() या pop()? (फेंको, जैसे EmptyStackException.)
डुप्लिकेट की अनुमति? (हाँ। मिन ट्रैकर का आम जाल यही है।)
क्या min() स्टैक नहीं बदलता? (हाँ। सिर्फ pop हटाता है।)

३. पहले सोचो

एक अकेली स्टैक क्यों काफी नहीं

अगर सिर्फ मान रखो, तो min() को पूरा स्कैन चाहिए: ओ(एन)। हर पॉप पर फिर स्कैन कर मिन गिन सकते हो। फिर भी सब ओ(१) नहीं। एक currentMin फील्ड कैश करो तो पॉप पर टूटता है: मौजूदा मिन हटाने के बाद पिछला मिन तभी पता चलता है जब तुमने उसे कहीं रखा हो।

तरीका क: मिन की दूसरी स्टैक (मुख्य हल)

दो स्टैक रखो:

१. values: असली डाटा, सामान्य लाइफो। २. mins: सिर्फ न्यूनतमों का इतिहास।

नियम:

पुश(x) पर: १. x हमेशा values पर धकेलो। २. अगर mins खाली है या x <= mins.peek(), तो x को mins पर भी धकेलो।
पॉप() पर: १. values से पॉप करो। २. अगर वह मान mins.peek() के बराबर है, तो mins से भी पॉप करो।
मिन() पर: mins.peek() लौटाओ (खाली जाँच के बाद)।

नया मिन लिखते समय <= इस्तेमाल करो, सिर्फ < नहीं। तब डुप्लिकेट मिन की हर कॉपी mins पर अपनी एंट्री पाती है, और हर डुप्लिकेट पॉप एक एंट्री सही से हटाता है।

तरीका ख: नोड पर अब-तक-का-मिन

हर स्टैक नोड (value, minWhenThisWasPushed) रखता है। x पुश करते समय नए नोड का मिन फील्ड min(x, previousTop.min) होता है (खाली स्टैक पर सिर्फ x)। फिर min() = top.min ओ(१) में। जगह फिर भी ओ(एन): हर नोड पर एक अतिरिक्त इंट, बजाय अक्सर छोटी दूसरी स्टैक के।

दोनों इंटरव्यू में सही जवाब हैं। दूसरी स्टैक खींचना आसान है। नोड फील्ड तब साफ है जब नोड टाइप तुम्हारे कंट्रोल में हो।

क्या न करो

स्टैक सॉर्ट करना (लाइफो क्रम टूटता है)।
हर min() पर स्कैन (ओ(१) शर्त चूकती है)।
सिर्फ पहला मिन रखना और अपडेट न करना (बड़े पुश और मिन के पॉप के बाद गलत)।

४. जावा हल

मुख्य डिज़ाइन: दो स्टैक। इंटरव्यू में स्पष्टता के लिए java.util.Stack; प्रोडक्शन में अक्सर ArrayDeque बेहतर।

import java.util.EmptyStackException;
import java.util.Stack;

/**
 * Stack that supports push, pop, peek, and min in O(1) time.
 * mins holds a history of new (or equal) minima.
 */
class StackWithMin {
    private final Stack<Integer> values = new Stack<>();
    private final Stack<Integer> mins = new Stack<>();

    public void push(int value) {
        values.push(value);
        if (mins.isEmpty() || value <= mins.peek()) {
            mins.push(value);
        }
    }

    public int pop() {
        if (values.isEmpty()) {
            throw new EmptyStackException();
        }
        int value = values.pop();
        if (value == mins.peek()) {
            mins.pop();
        }
        return value;
    }

    public int min() {
        if (mins.isEmpty()) {
            throw new EmptyStackException();
        }
        return mins.peek();
    }

    public int peek() {
        if (values.isEmpty()) {
            throw new EmptyStackException();
        }
        return values.peek();
    }

    public boolean isEmpty() {
        return values.isEmpty();
    }
}

पुश ५, ३, ७, ३ फिर दो पॉप का चरण:

चरण	मान (तल → ऊपर)	मिन-स्टैक	मिन()
पुश ५	५	५	५
पुश ३	५, ३	५, ३	३
पुश ७	५, ३, ७	५, ३	३
पुश ३	५, ३, ७, ३	५, ३, ३	३
पॉप (३)	५, ३, ७	५, ३	३
पॉप (७)	५, ३	५, ३	३

ध्यान दो: ७ कभी mins में नहीं आया। दूसरा ३ आया, इसलिए ३ का पहला पॉप के बाद भी मिन = ३ रहता है।

वैकल्पिक स्केच: हर नोड पर मिन

class NodeWithMin {
    final int value;
    final int min; // smallest value in the stack when this node is at the top

    NodeWithMin(int value, int min) {
        this.value = value;
        this.min = min;
    }
}

class StackWithMinNodes {
    private final Stack<NodeWithMin> stack = new Stack<>();

    public void push(int value) {
        int newMin = stack.isEmpty() ? value : Math.min(value, stack.peek().min);
        stack.push(new NodeWithMin(value, newMin));
    }

    public int pop() {
        return stack.pop().value;
    }

    public int min() {
        return stack.peek().min;
    }
}

वही ओ(१) संक्रियाएँ। अतिरिक्त जगह हमेशा प्रति तत्व एक इंट, छोटी मिन-स्टैक नहीं।

५. जटिलता तालिका

तरीका	पुश	पॉप	मिन	अतिरिक्त जगह	नोट
मिन के लिए पूरी स्टैक स्कैन	ओ(१)	ओ(१)	ओ(एन)	ओ(१)	ब्रीफ फेल
सिर्फ पॉप पर मिन दोबारा गिनना	ओ(१)	ओ(एन)	ओ(१)	ओ(१)	फिर भी सब ओ(१) नहीं
मिन की दूसरी स्टैक	ओ(१)	ओ(१)	ओ(१)	ओ(एन) सबसे खराब, अक्सर कम	यहाँ मुख्य जवाब
हर नोड पर मिन फील्ड	ओ(१)	ओ(१)	ओ(१)	ओ(एन) हमेशा	नोड कंट्रोल हो तो साफ

एन = स्टैक में तत्वों की संख्या। दोनों अच्छे जवाब सबसे खराब स्थिति में रैखिक अतिरिक्त मेमोरी लेते हैं। उम्मीद यही है: अचर-समय मिन के लिए जगह खरीद रहे हो।

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

खाली स्टैक फिर मिन() या पॉप() → फेंको। समस्या न कहे तो Integer.MAX_VALUE जैसा जादुई नंबर न लौटाओ।
एक तत्व → एक पुश, मिन वही, पॉप के बाद खाली; बिना जाँच मिन न बुलाओ।
मिन के डुप्लिकेट → mins पर पुश करते समय <=। सिर्फ सख्त < से उसी मिन की दो कॉपी पहले पॉप पर टूट जाती हैं।
सख्त बढ़ता क्रम (१, २, ३, ४) → mins में सिर्फ १। ठीक।
सख्त घटता क्रम (४, ३, २, १) → हर पुश मिन अपडेट करता है। mins values के साथ बढ़ता है।
वैश्विक मिन पॉप, ऊपर बड़ा मान बचा → पिछला मिन इतिहास (या पिछले नोड के मिन फील्ड) से वापस आना चाहिए।

आम गलतियाँ:

१. मिन स्टैक के लिए < बजाय <= न लगाना। डुप्लिकेट मिन टूटते हैं। २. हर pop पर हमेशा mins पॉप करना। गलत जब हटाया मान मौजूदा मिन न हो। ३. किसी भी स्टैक पर peek से पहले खाली जाँच भूलना। ४. values स्कैन कर मिन लौटाना और फिर भी ओ(१) कहना। ५. min() के अंदर स्टैक बदलना। मिन पूछताछ है, विनाशक संक्रिया नहीं।

७. दोस्त को समझाने वाला सार

स्टैक मिन माँगता है: पुश, पॉप, और "अभी सबसे छोटा मान क्या है?" तीनों अचर समय में।

१. सादा स्टैक बिना स्कैन मिन नहीं बताता। २. मिन की दूसरी स्टैक रखो (या हर नोड पर अब-तक-का-मिन)। ३. पुश पर नया मिन तभी लिखो जब नया मान पुराने मिन से छोटा या बराबर हो। ४. पॉप पर मिन एंट्री तभी हटाओ जब हटाया मान वही मिन हो। ५. खाली स्टैक और डुप्लिकेट मिन पर नजर। यहीं आमतौर पर बग होते हैं।

अगर पुश ५, ३, ७, ३ के लिए दोनों स्टैक खींच सको और समझा सको दूसरा ३ क्यों मायने रखता है, तो समस्या ३.२ तुम्हारी है।