문제 링크
https://leetcode.com/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150
문제 해석
- MinStack 구현
- push , pop , top 같은 기본적 함수도 구현
- 가장 작은 값 return 하는 getMin 함수 존재
문제 해결
- 최소 값을 저장하는 배열을 따로 만들자
Why?
- 변수 하나에 저장 시 , 최소값을 삭제시 찾으려 계속 순회 해야함!
- 현재 최소값 배열보다 , 더 작은 값이 나올 시 최소값 배열에 추가하자!
- 삭제할 때 , 최소값 배열 의 값과 일치하는지 확인
슈도 코드
- Push
if min[last]>=val:
min.append(val)
- pop
if min[mlast]==val:
min.pop()
- getMin
return min[last]- 결국 , 가장 큰 값을 향해 가므로 , 답이 나온다.
결과
사담
되게 자주 사용하고 보는 스택인지라, 빨리 풀었으나
최소값을 리턴하는 스택인 문제를 보며 스택을 도와주는 자료구조가 있고 없는게 얼마나 효율성에 큰 차이를 주는지에 대해서 깨달은 것 같다.
메모본
Continuous Learning