Leetcode——556. 下一个更大元素 III

题目链接：556. 下一个更大元素 III

（由于图片上传失败，不贴原题目了，有需要可以前往力扣查看）

本文给出该题的单调栈做法，同时绕过所有库函数，所有逻辑均自行实现。

本题的思路就是从右向左按位遍历，找到第一次下降时的下标，同时将数字对于下标填入栈中。这样，当找到要更改的下标时，开始循环，找到最后一个比要被替换的数字大的值，这就是单调栈。互换二者位置。我们假设第一次下降时下标为 idx , 被替换下标为 change, 由之前逻辑可以知道，[idx + 1, change - 1]的数字均大于idx的数字,[change + 1, size - 1]位置的数均小于idx的数字，最后我们只需要将[idx + 1, size - 1]位置的所有数字调换顺序就保证为下一个更大的数字，而不必使用排序。

而以上所需的交换swap，逆序reverse，还有离散化数字和重组数字，代码都给予实现。

class Solution {
public:int nextGreaterElement(int n) {int cnt = 0;    // 位数vector<int> nums;   // 离散化for(int i = n; i > 0; i /= 10){nums.push_back(i % 10);cnt++;}reverse(0, cnt - 1, nums);    // 更直观stack<int> stk;stk.push(cnt - 1);for(int i = cnt - 2; i >= 0; i--){if(nums[i] < nums[i + 1]){// 找到第一次下降的下标 iint change;        // 被更换位置while(!stk.empty() && nums[i] < nums[stk.top()]){change = stk.top();stk.pop();}swap(i, change, nums);reverse(i + 1, cnt - 1, nums);    // 注意下标long long ans = funcToll(nums);if(ans > INT_MAX){return -1;}else{return (int)ans;}}stk.push(i);    // 别忘在没找到前将下标入栈备用}return -1;}// 逆序void reverse(int i, int j, vector<int>& nums){if(i < 0 || j >= nums.size() || i >= j) { return; }while(i < j){swap(i++, j--, nums);}}// 交换void swap(int i, int j, vector<int>& nums){if(i < 0 || i >= nums.size() || j < 0 || j >= nums.size()) { return; }int t = nums[i];nums[i] = nums[j];nums[j] = t;}// 重组数字long long funcToll(vector<int>& nums){long long ans = 0;for(int x : nums){ans = ans * 10 + x;}return ans;}
};