C ++中的下一个Greater Element III

假设我们有一个正的32位整数n，我们需要找到最小的32位整数，该整数与整数n中存在的数字完全相同，并且值大于n。如果我们没有这样的正32位整数，则返回-1。

因此，如果数字为213，则结果将为231。

为了解决这个问题，我们将遵循以下步骤-

• s：= n作为字符串，sz：= s的大小，确定：= false

• 当我在sz范围内– 2到0

• 如果s [i] <s [i + 1]，则ok：= true并中断循环

• 如果of为假，则返回– 1

• 最小：= i，curr：= i + 1

• 对于范围i + 1至sz – 1中的j

• id s [j]> s [smallest]和s [j] <= s [curr]，然后curr：= j

• 与s [curr]交换s [smallest]

• aux：= s的子串，从索引0到最小

• 反向辅助

• ret：= s的子串，从索引0到最小+ aux

• 如果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