LeetCode556：下一个更大元素（|||）

题目：

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

示例 1：

输入：n = 12
输出：21

示例 2：

输入：n = 21
输出：-1

提示：

• 1 <= n <= 2^31 - 1

这次寻找下一个更大的元素就是将所给的n分成各个数字，然后组拼成一个比n大的数，注意这个数是比n大一点，如果有两个比n大的数，则取的是两个数的最小。

思路：先将n按照除余方法将各个数字存放在数组中，需要用reverse（）函数反转过来。通过特定条件的位置进行互换位置，最后直接用for（）拼成好下一个更大的元素。

第一步直接定义好需要保存数字的数组、存放数组、反转数组。

        int x;int res = 0;vector nums;long target = 0;while (n > 0){x = n % 10;n = n / 10;nums.push_back(x);}reverse(nums.begin(), nums.end());

这里用long类型定义的target是为了防止找出数据下一个元素时超出INT_MAX。索性直接用long定义。

先将两种特殊情况考虑在内是：

①n已经是各个数字组成的最大数，直接返回-1.

        for (int i = 1; i < nums.size(); i++)  //来判断数值是否全部递减 3210{if (nums[i] > nums[i - 1]){res = res + 1;}}

②当下一个更大数直接超出INT_MAX，也直接返回-1

            if (target > INT_MAX||res==0){target = -1;}

考虑完这两种特殊情况后，就要管一般的情况：

我们找寻下一个更大的元素时，遵循的原则就是    能动个位不动十位，能动十位不动百位。

所以我们直接倒序查找，如果下一个元素比当前元素大时，直接遍历过。如果下一个元素比当前元素小时，将下一个元素赋值给新定义的变量。再次从倒序遍历，找到第一个比变量大的元素，进行互换位置。从第一个变量的下标到数组末尾，全部反转一遍。其实用sort（）函数从小到大排序也行，意义相同。

int temp1=0;int temp2=0;for (int i = nums.size() - 2; i >= 0; i--){if (nums[i] < nums[i + 1]){temp1 = i;break;}}for (int i = nums.size() - 1; i >= 0; i--){if (nums[i] > nums[temp1]){temp2 = i;break;}}swap(nums[temp1], nums[temp2]);reverse(nums.begin() + 1 + temp1, nums.end());

这样就已经把一般情况给表达完成了。

最后写出target数值，检验是否符合题目要求。

            for (int i = 0; i < nums.size(); i++){target = target * 10 + nums[i];}

完整代码：

class Solution
{
public:int nextGreaterElement(int n){int x;int res = 0;vector nums;long target = 0;while (n > 0){x = n % 10;n = n / 10;nums.push_back(x);}reverse(nums.begin(), nums.end());for (int i = 1; i < nums.size(); i++)  //来判断数值是否全部递减 3210{if (nums[i] > nums[i - 1]){res = res + 1;}}int temp1=0;int temp2=0;for (int i = nums.size() - 2; i >= 0; i--){if (nums[i] < nums[i + 1]){temp1 = i;break;}}for (int i = nums.size() - 1; i >= 0; i--){if (nums[i] > nums[temp1]){temp2 = i;break;}}swap(nums[temp1], nums[temp2]);reverse(nums.begin() + 1 + temp1, nums.end());for (int i = 0; i < nums.size(); i++){target = target * 10 + nums[i];}if (target > INT_MAX||res==0){target = -1;}return target;}
};

感谢各位读者的阅读！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！