【单调栈】下一个更大元素 III

Tag

【单调栈】【数组】【字符串】

---

题目来源

556. 下一个更大元素 III

---

题目解读

找出大于整数的最小整数，这个最小整数必须由原来整数中出现的数字组成。

---

解题思路

方法一：下一个排列

我们将 n 转换成字符串之后，本题就是在求字符数组的 31. 下一个排列。直接贴出代码如下：

实现代码

class Solution {
public:
    int nextGreaterElement(int n) {
        string str = to_string(n);
        int strLen = str.size();
        int i = strLen - 2;
        // 找str中违反字符数字是降序的第一个字符（从后往前的第一个）
        while (i >= 0 && str[i] >= str[i+1]) {
            --i;
        }
        if (i < 0) return -1;                       // str 字符数字是降序的，无答案

        // 找 str[i] 右侧比 str[i] 大的最小的字符
        int j = strLen - 1;
        while (j >= 0 && str[i] >= str[j]) {
            --j;
        }
        swap(str[i], str[j]);
        reverse(str.begin() + i + 1, str.end());    // 也可以进行排序
        long res = stol(str);
        return res > INT_MAX ? -1 : res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

单调栈

找 str[i] 右侧比 str[i] 大的最小的字符，可以使用单调栈来解决。直接贴上代码：

class Solution {
public:
    int nextGreaterElement(int n) {
        string str = to_string(n);
        int strLen = str.size();

        int i = strLen - 1;
        int idx = 0;        // 找 `str[i]` 右侧比 `str[i]` 大的最小的字符
        stack<int> stk;
        
        for (; i >= 0; --i) {
            // 如果从后往前一直是递增的就一直加入栈，直到遇到违反递增的第一个字符，下标为i，找到idx
            while(!stk.empty() && str[i] < str[stk.top()]) {
                idx = stk.top();
                stk.pop();
            }
            // 将 str[i] 与其右侧比 str[i] 大的最小字符交换
            if (idx != 0) {
                swap(str[i], str[idx]);
                break;
            }
            stk.push(i);
        }
        // idx 一直没有更新，说明 str 从后往前一直是递增的
        if (idx == 0) return -1;
        reverse(str.begin() + i + 1, str.end());    // 也可以进行排序
        long res = stol(str);
        return res > INT_MAX ? -1 : res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

复杂度分析

时间复杂度：$O(logn)$，$m$ 是整数 n 转化成字符串后的长度，其实有 m = logn，本题需要对长度为 $m$ 的字符进行一次遍历操作，因此时间复杂度为 $O(m)$，即 $O(logn)$。

空间复杂度：$O(logn)$，使用的额外字符串，长度为 $O(logn)$。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。