[LeetCode] 155. Min Stack

https://leetcode.com/problems/min-stack/

Min Stack - LeetCode

 

이 문제의 핵심은 getMin이다. O(1)의 시간복잡도를 가지면서 Stack에서 최소값을 조회하려면 어떻게 해야할까?

답은 minStack을 하나 더 두어,Push와 pop을 할때(즉,Data에 변화가 있을때) Min Stack에는 현재의 min 요소를 추가하도록 하는것이다. 이렇게 하면 최소값을 조회할때 맨 상단의  값을 리턴하면된다.

---

SOLUTION CODE

# PYTHON

# Best Code
class MinStack:

    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val,self.minStack[-1] if self.minStack else val)
        self.minStack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.Minstack.pop()


    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

 

# C++ 내풀이 : 스택사용

#include <iostream>
#include <string>
#include <stack>


class MinStack {

    int min=0;
    stack<int> s;
    stack<int> m;

public:
    MinStack() {
        min=0;
    }
    
    void push(int val) {
        s.push(val);
        
        if(m.empty()){ // m이 비어있을때
            m.push(val);

        }
        else if(m.top()>=val){ // val이 최소값일때
            m.push(val);
        }
        else{
            int t = m.top();
            m.push(t);
        }
    }
    
    void pop() {
        s.pop();
        m.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return m.top();
    }
};

# C++ Best Code (스택에 pair<현재값,현재의 최소값> 을 넣어준다.)

class MinStack {
public:
    vector< pair<int,int> > s;
	
    MinStack() { }
    
    void push(int val) {
        if(s.empty())
            s.push_back({val,val});
        else
            s.push_back({val,min(s.back().second,val)});    
    }
    
    void pop() { s.pop_back(); }
    
    int top() { return s.back().first; }
    
    int getMin() { return s.back().second; }
};