양의 32비트 정수 n이 있다고 가정하고 정수 n에 존재하는 정확히 동일한 자릿수를 갖고 값이 n보다 큰 가장 작은 32비트 정수를 찾아야 합니다. 그러한 양의 32비트 정수가 없으면 -1을 반환합니다.
따라서 숫자가 213이면 결과는 231이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- s :=n을 문자열로, sz :=s의 크기, ok :=false
- sz – 2에서 0 사이의 i에 대해
- s[i]
- s[i]
- of가 거짓이면 1을 반환합니다.
- 가장 작은 :=i, curr :=i + 1
- i + 1 ~ sz – 1 범위의 j에 대해
- id s[j]> s[가장 작은] 및 s[j] <=s[curr], 다음 curr :=j
- s[smallest]를 s[curr]로 교환
- aux :=인덱스 0에서 가장 작은 s의 부분 문자열
- 역보조
- ret :=인덱스 0에서 가장 작은 + aux까지 s의 부분 문자열
- ret가> 32비트 + ve 정수 범위이면 -1을 반환하고, 그렇지 않으면 ret
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
int sz = s.size();
int i;
bool ok = false;
for(i = sz - 2; i >= 0; i--){
if(s[i] < s[i + 1]) {
ok = true;
break;
}
}
if(!ok) return -1;
int smallest = i;
int curr = i + 1;
for(int j = i + 1; j < sz; j++){
if(s[j] > s[smallest] && s[j] <= s[curr]){
curr = j;
}
}
swap(s[smallest], s[curr]);
string aux = s.substr(smallest + 1);
reverse(aux.begin(), aux.end());
string ret = s.substr(0, smallest + 1) + aux;
return stol(ret) > INT_MAX ? -1 : stol(ret);
}
};
main(){
Solution ob;
cout << (ob.nextGreaterElement(213));
} 입력
213
출력
231