[leetcode]556-下一个更大的元素III

马谦马谦马谦

615
文章

17
评论

2020年2月11日09:59:00数据结构和算法评论266字数 1529阅读5分5秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/next-greater-element-iii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。

示例 1：

输入: 12
输出: 21

示例 2：

输入: 21
输出: -1

二、题目解析

题目意思梳理：给定一个数字n（假设是523486，六位数），用同样的数字组成（5、2、3、4、8、6）组合成另外一个六位数，要求这个新组成的数字是所有组合中第一个大于原数字的。注意n是32位的正整数，如果不存在的话返回-1。

看完题目可能并没有好的思路，可以先考虑一下，什么场景下会不存在这个数字。例如：

99999
98765
33322

可以看出的一个规律是：如果数字都是降序排列的话，是找不到一个比它大数字的。为什么呢？如果一个数，低位的数字比高位的数字都小，那么不可能存在一种办法可以把低位较小的数字放到高位去反而比原来的数字还要大的。

只存在一种情况就是把低位较大的数字和高位较小的数字对换才会比原来数字大。那也就说明，如若要找到一个比原来数大的组合，这n的内部一定存在一个数，比它右边的数字要小。进而就说明，从低位往高位，一定存在降序数列。例如：

95876 ==> 96578
82431 ==> 83124

在知晓了这个情况之后，如何取得最小值呢？

以95876为例，从低位往高位数，第一个降序的位置是[..., 5, 8, ...]，如果在这里用一个低位的大于5的数字替换掉它就可以得到一个大于95876的数字了。那么如何替换才能最小？肯定是把右边大于5的最小的数字替换过来才最小，也就是用6来替换了，替换后得到96875。

96875是最小的吗？不是，96578才是最小。96875和96578有什么区别？最后三位数字排序不一样，一个升序排列，一个降序排列。降序排列数字由大到小，排列出来肯定是大于升序序列的。

所以能总结出来的操作是：

从低位往高位寻找到一个降序序列[i, i+1]，记录下i的位置。如果不存在这个序列，说明不存在符合条件的数字。
如果找到了i，从i的右边开始，找到一个最小的大于i的数字，替换它。
最后把i右边的数据反转，得到一个升序序列。

除此之外，还有一个要注意的问题是要考虑数据溢出，可能原始数据没有溢出，但是比它大的那个数字就溢出了。例如1999999999，比它大的最小的数字是9199999999，这个数字溢出了。

三、代码实现

3.1 考虑数字溢出

leetcode第七题“正数反转”就已经遇到过这个问题了。假设抓换后的当前数字为x，新计算出来的x = x * 10 + y。当x > INT_MAX / 10 或者x == INT_MAX / 10 && y > 7的时候，计算x会溢出，具体的可以参考：[leetcode]7-整数反转。

3.2 数字反转

需要实现一个函数，反转固定区间内的数字：

/*
 * 反转数组，左闭右开区间[left, right)。
 * @left 左下标，包含当前值
 * @right 右下标，不包含当前值
 */
void reverse(vector<int> &v, size_t left, size_t right) {
    int tmp;
    size_t idx;
    for (idx = left; idx < (left + right) / 2; idx++) {
        tmp = v[idx];
        v[idx] = v[right - 1 - (idx - left)];
        v[right - 1 - (idx - left)] = tmp;
    }
}

* 反转数组，左闭右开区间[left, right)。

* @left 左下标，包含当前值

* @right 右下标，不包含当前值

void reverse(vector<int> &v, size_t left, size_t right) {

int tmp;

size_t idx;

for (idx = left; idx < (left + right) / 2; idx++) {

tmp = v[idx];

v[idx] = v[right - 1 - (idx - left)];

v[right - 1 - (idx - left)] = tmp;

}

3.3 交换函数

void my_swap(int &a, int &b) {
    int c = a;
    a = b;
    b = c;
}

void my_swap(int &a, int &b) {

int c = a;

a = b;

b = c;

}

3.4 实现

int nextGreaterElement(int n) {
    int x = n, output = 0;
    int i, dec_idx = -1, y;
    vector<int> v;

    // 按位放到数组中去，并按照逻辑顺序把数组反转
    while (x) {
        v.push_back(x % 10);
        x /= 10;
    }
    reverse(v, 0, v.size());

    // 找到第一个下降的元素下标
    for (i = v.size() - 1; i > 0; i--) {
        if (v[i] > v[i - 1]) {
            dec_idx = i - 1;
            break;
        }
    }
    // 没有找到
    if (i == 0)
        return -1;

    // y是最小的大于v[dec_idx]的元素的下标，它不可能是-1，一定能找到
    y = dec_idx + 1;
    for (i = dec_idx + 2; i < v.size(); i++) {
        if (v[i] > v[dec_idx] && v[i] <= v[y]) {
            y = i;
        }
    }

    // 交换
    my_swap(v[dec_idx], v[y]);
    // 反转右边的数字
    reverse(v, dec_idx + 1, v.size());

    // 把数组转换成单个数字
    for (i = 0; i < v.size(); i++) {
        // 处理数据溢出
        if (output > INT_MAX / 10 || (output == INT_MAX && v[i] > (INT_MAX % 10)))
            return -1;
        output = output * 10 + v[i];
    }

    return output;
}

int nextGreaterElement(int n) {

int x = n, output = 0;

int i, dec_idx = -1, y;

vector<int> v;

// 按位放到数组中去，并按照逻辑顺序把数组反转

while (x) {

v.push_back(x % 10);

x /= 10;

}

reverse(v, 0, v.size());

// 找到第一个下降的元素下标

for (i = v.size() - 1; i > 0; i--) {

if (v[i] > v[i - 1]) {

dec_idx = i - 1;

break;

}

// 没有找到

if (i == 0)

return -1;

// y是最小的大于v[dec_idx]的元素的下标，它不可能是-1，一定能找到

y = dec_idx + 1;

for (i = dec_idx + 2; i < v.size(); i++) {

if (v[i] > v[dec_idx] && v[i] <= v[y]) {

y = i;

}

// 交换

my_swap(v[dec_idx], v[y]);

// 反转右边的数字

reverse(v, dec_idx + 1, v.size());

// 把数组转换成单个数字

for (i = 0; i < v.size(); i++) {

// 处理数据溢出

if (output > INT_MAX / 10 || (output == INT_MAX && v[i] > (INT_MAX % 10)))

return -1;

output = output * 10 + v[i];

}

return output;

}

在题解中看到的一个可以优化的点是：找到i后，从i开始往右边找到一个最小的大于它的数字，可以使用二分查找来完成。不过题目限制的是32位整数，总共不超过10位，个人认为优化不明显。

实际测试中，使用这个二分法查找，执行耗时更短。

[leetcode]556-下一个更大的元素III

四、单元测试

测试案例的后面几个都是leetcode提交中出错的案例：

TEST(nextGreaterElement, leetcode) {
    Solution s;
    EXPECT_EQ(s.nextGreaterElement(877645132), 877645213);
    EXPECT_EQ(s.nextGreaterElement(12), 21);
    EXPECT_EQ(s.nextGreaterElement(21), -1);
    EXPECT_EQ(s.nextGreaterElement(12222333), 12223233);
    EXPECT_EQ(s.nextGreaterElement(12443322), 13222344);
    EXPECT_EQ(s.nextGreaterElement(1999999999), -1);
}