समस्या
A generic Stack<T> किसी भी type के लिए काम करता है. यहाँ आप इस idea को आगे बढ़ाते हैं: integers का एक stack, जो constant time में अपना minimum भी report कर सके.
Operations को order में process करें:
push <x>: x को push करें.pop: top value हटाएँ (जब stack empty हो, तो ignore करें).min: stack में अभी मौजूद सबसे छोटी value report करें, या अगर यह empty हो तो -1.
min_stack_operations(operations) implement करें.
Input
operations: The operations.
Output
Return the answers of the min operations, in order.
सीमाएँ
1 ≤ ऑपरेशन की संख्या ≤ 200,000
0 ≤ x ≤ 10^9
उदाहरण
इनपुट:
operations = ["push 5", "push 3", "min", "pop", "min"]
अपेक्षित आउटपुट:
expected = [3, 5]इनपुट:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 5};इनपुट:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 5};व्याख्या
जब stack पर 5 और 3 हैं, minimum 3 है. 3 को pop करने के बाद केवल 5 बचता है: [3, 5].
इनपुट:
operations = ["min", "pop", "push 7", "min"]
अपेक्षित आउटपुट:
expected = [-1, 7]इनपुट:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {-1, 7};इनपुट:
string[] operations = new string[] {"min", "pop", "push 7", "min"};
अपेक्षित आउटपुट:
long[] expected = new long[] {-1, 7};व्याख्या
Empty stack -1 report करता है और pop ignore हो जाता है; फिर minimum 7 है: [-1, 7].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर मान के साथ उस समय के स्टैक का न्यूनतम भी रखें।
संकेत 2
तब मौजूदा न्यूनतम बस दूसरे स्टैक का सबसे ऊपर वाला मान है।
संकेत 3
खाली स्टैक पर pop अनदेखा करें, और खाली होने पर min के लिए -1 दें।
अपेक्षित जटिलता
समय O(ऑपरेशन की संख्या), अतिरिक्त स्थान O(ऑपरेशन की संख्या)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।