원형 배열(마지막 요소의 다음 요소가 배열의 첫 번째 요소임)이 있다고 가정하면 모든 요소에 대해 다음 큰 숫자를 표시해야 합니다. 여기에서 숫자 x의 다음 큰 숫자는 배열에서 순회 순서 다음으로 큰 첫 번째 숫자입니다. 이는 다음 큰 숫자를 찾기 위해 순환적으로 검색할 수 있음을 의미합니다. 존재하지 않으면 -1이 됩니다. 따라서 숫자가 [1, 2, 1, 3, 2, 1]이면 출력은 [2,3,3,-1,3,2]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=배열의 크기
- 크기가 n인 res라는 배열 하나를 정의하고 이것을 -1로 채우고 하나의 스택 st를 정의합니다.
- 0에서 2n 사이의 i에 대해
- 인덱스 :=i mod n, x :=nums[인덱스]
- st가 비어 있지 않고 nums[스택 상단]
- res[스택 상단] :=x
- 스택에서 최상위 요소 삭제
- 스택에 인덱스 삽입
예(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector <int> res(n, - 1);
stack <int> st;
for(int i = 0; i < 2 * n; i++){
int idx = i % n;
int x = nums[idx];
while(!st.empty() && nums[st.top()] < x){
res[st.top()] = x;
st.pop();
}
st.push(idx);
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,3,2,1};
print_vector(ob.nextGreaterElements(v));
} 입력
[1,2,1,3,2,1]
출력
[2,3,3,-1,3,2]