2022-07-03

[Zheaoli]

2022-07-03

[dreamhunter2333]

#include <algorithm>
#include <string>
using namespace std;
/*
 * @lc app=leetcode.cn id=556 lang=cpp
 *
 * [556] 下一个更大元素 III
 */

// @lc code=start
class Solution
{
public:
    int nextGreaterElement(int n)
    {
        auto nums = to_string(n);
        for (size_t i = nums.size() - 1; i > 0; i--)
        {
            if (nums[i] <= nums[i - 1])
                continue;
            int max_i = i;
            for (size_t j = i + 1; j < nums.size(); j++)
            {
                if (nums[j] > nums[i - 1])
                    max_i = j;
            }
            swap(nums[i - 1], nums[max_i]);
            reverse(nums.begin() + i, nums.end());
            long ans = stol(nums);
            return ans > INT_MAX ? -1 : ans;
        }
        return -1;
    }
};
// @lc code=end

---

微信id: 而我撑伞 来自 vscode 插件

[SaraadKun]

556. 下一个更大元素 III

class Solution {
    public int nextGreaterElement(int n) {
        List<Integer> list = new ArrayList<>();
        while (n > 0) {
            list.add(n % 10);
            n /= 10;
        }
        boolean flag = true;
        for (int i = 1; i < list.size(); i++) {
            //找到第一个高位数字小于低位数字的位置,此时[0, 高位数字)为升序
            if (list.get(i - 1) > list.get(i)) {
                //从低位向高位遍历,找到第一个大于高位的数字,交换位置
                for (int j = 0; j < i; j++) {
                    if (list.get(j) > list.get(i)) {
                        swap(list, j, i);
                        break;
                    }
                }
                //此时[0, 高位)为升序,翻转此区间,并修改标记
                for (int lo = 0, hi = i - 1; lo < hi; lo++, hi--) {
                    swap(list, lo, hi);
                }
                flag = false;
                break;
            }
        }
        //上轮循环未找到符合要求的数字,则n没有满足题意的数字
        if (flag) {
            return -1;
        }
        long sum = 0;
        //结果大于2^31 - 1,返回 -1
        for (int i = list.size() - 1; i >= 0; i--) {
            sum = sum * 10 + list.get(i);
            if (sum > Integer.MAX_VALUE) {
                return -1;
            }
        }
        return (int) sum;
    }

    void swap(List<Integer> list, int lo, int hi) {
        int tmp = list.get(lo);
        list.set(lo, list.get(hi));
        list.set(hi, tmp);
    }
}

---

WeChat: Saraad