반응형
여러분, 안녕하세요. STACK은 다 알고 있는데 단조로운 스택이란 무엇일까요?
Monotonic Stack is a special variation of the typical data structure Stack and appeared in many interview questions.
As its name shows, monotonic stack contains all features that a normal stack has and its elements are all monotonic decreasing or increasing.
It just uses some ingenious logic to keep the elements in the stack orderly (monotone increasing or monotone decreasing) after each new element putting into the stack.Leetcode의 문제 이름: 다음으로 큰 원소 I
배열에서 x 요소의 다음으로 큰 요소는 같은 배열에서 x의 오른쪽에 있는 첫 번째 큰 요소입니다.
제약 조건: 배열의 모든 정수는 양수이며 고유합니다.
예를 들어 보겠습니다.
Given Array, arr : [7,2,1,6,9,5,4]배열의 길이가 L이라고 가정하자. 여기서 L = 7
배열의 각 요소에서 다음으로 큰 요소를 찾아야 합니다. 주어진 요소에 대해 다음으로 큰 요소가 없으면 해당 요소에 대해 -1을 반환합니다.
먼저 크기가 L인 빈 스택을 생성합니다(예: S1={}).
스택 S1, S1 = {7}에서 어레이의 첫 번째 요소 푸시
이제 스택에 배열의 다른 요소를 삽입하기 시작할 때 삽입 요소가 스택의 맨 위 요소보다 작아야 한다는 점에 유의해야 합니다. 삽입 요소가 크면 스택에서 모든 요소를 제거한 다음 요소를 삽입하고 다음 큰 요소로 삽입 요소를 매핑해야 합니다.
이렇게 하면 배열의 각 요소와 그 다음 큰 요소의 매핑을 가져오고 스택 S1에 남아 있는 요소에는 다음 큰 요소가 없으므로 해당 요소에 대해 -1을 반환합니다.
시간 복잡도 : O(N)
공간 복잡도 : O(N)
이 문제의 다른 변형:
- 다음으로 작은 원소
[이 경우 다음 작은 원소를 만나면 스택에서 튀어나오며, 다른 것들은 다음 큰 원소를 기준으로 유사합니다.] - 이전의 더 큰 요소
[여기서 배열을 역순으로 이동하고 다음으로 큰 요소를 만날 때 스택에서 뜹니다.] - 이전의 더 작은 요소
[이 경우 배열은 역순으로 이동하고 다음으로 작은 요소를 만나면 스택에서 뜹니다.]
참조:
- 양주의 단조로운 스택
- 모노톤 스택(다음의 큰/작은 코드 )
- 단조로운 스택을 사용한 Java 솔루션
- 스택을 사용하지 않는 Java 솔루션
To connect or collaborate ping me:
LinkedIn
Twitter
GitHub
댓글