Open seungriyou opened 8 months ago
https://leetcode.com/problems/min-stack/
일반적인 용도로 쓸(즉, val을 저장할) stack과 최솟값을 기록하는 용도로 쓸 min_stack을 유지한다. (2-stack)
val
stack
min_stack
.push(val) 시, 다음의 조건 중 하나에 해당하면 min_stack에도 val을 추가해준다.
.push(val)
.pop() 시, stack에서 pop 한 값이 min_stack의 top과 같다면, min_stack도 pop 해준다.
.pop()
pop
.getMin() 시, min_stack이 비어있지 않다면 min_stack의 top을, 비어있다면 stack의 top을 반환한다.
.getMin()
조금만 생각을 해보면, Idea 1에서 따로 유지했던 min_stack을 사용하지 않고도 stack에 튜플 값 (val, min_val)을 저장함으로써 구현할 수 있다! 😢 이렇게 하면 전체적으로 구현이 더 간단해진다.
(val, min_val)
O(n)
Approach
Idea 1 (2-Stack ver)
일반적인 용도로 쓸(즉,
val을 저장할)stack과 최솟값을 기록하는 용도로 쓸min_stack을 유지한다. (2-stack).push(val)시, 다음의 조건 중 하나에 해당하면min_stack에도val을 추가해준다.min_stack이 비어있거나val이min_stack의 top이 작거나 같으면.pop()시,stack에서 pop 한 값이min_stack의 top과 같다면,min_stack도pop해준다..getMin()시,min_stack이 비어있지 않다면min_stack의 top을, 비어있다면stack의 top을 반환한다.Idea 2 (1-Stack ver) 💡
조금만 생각을 해보면, Idea 1에서 따로 유지했던
min_stack을 사용하지 않고도stack에 튜플 값(val, min_val)을 저장함으로써 구현할 수 있다! 😢 이렇게 하면 전체적으로 구현이 더 간단해진다.Complexity
O(n)O(n)