继续冲~

503. Next Greater Element II

Analysis

这跟之前做的那个温度题很像，应该都是单调栈的题目。不过不同的是，这个题返回的值是遍历顺序的第一个大的值。也就是说，如果这个元素后面不存在比它大的数，那么就循环的从开头遍历到这个元素，找出比它大的第一个元素。

Code

method 1

很自然就想到暴力解法了：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
      int size = nums.size();
      vector<int> ret(size);
      for(int i = 0; i < size; i++) {
        int left = 0, right = i + 1;
            while(right < size && nums[right] <= nums[i]) right++;
            while(left < i && nums[left] <= nums[i]) left++;
            if(right != size) ret[i] = nums[right];
            else if(left != i) ret[i] = nums[left];
            else ret[i] = -1;
      }
      return ret;
    }
};

嗯，这个解法是可以通过的。实际上，在向右遍历的过程中如果找到了，就没有必要再向左找了，所以可以优化一下：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
      int size = nums.size();
      vector<int> ret(size);
      for(int i = 0; i < size; i++) {
        int pre = 0, rear = i + 1;
        bool flag = false;
            while(rear < size) {
              if(nums[rear] > nums[i]) {
                ret[i] = nums[rear];
                flag = true;
                break;
              }
              rear++;
            }
            if(flag) continue;
            else {
              while(pre < i) {
                if(nums[pre] > nums[i]) {
                  ret[i] = nums[pre];
                  break;
                }
                pre++;
              }
              if(pre == i) ret[i] = -1;
            }
      }
      return ret;
    }
};

相比上一段代码而言，时间消耗减少了 3 倍...不过依然不是一个好解法。

method 2

正如前面所说，这个题还可以用单调栈的思路来解决。
不过，这个题还有一个不一样的地方，如果这个数字后没有比它更大的数了，就需要循环的从头开始查找。但是，单调栈只能找到这个元素后面第一个比它大的元素啊。
实际上，这里有一个简单的做法，那就是重新在遍历一次，这有点类似循环队列。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int size = nums.size();
        vector<int> ret(size, -1);
        stack<int> st;
        for(int i = 0; i < size * 2 - 1; i++) {
            while(!st.empty() && nums[st.top()] < nums[i % size]) {
                ret[st.top()] = nums[i % size];
                st.pop();
            }
            st.push(i % size);
        }
        return ret;
    }
};

重复的遍历过程，可以用取余运算替代。
仔细想想，一次遍历结束后，对于一个元素而言，如果其后面存在比它大的元素，那么比这个元素大的第一个元素就找到了。对应的，第二次遍历的时候就不用入栈了，所以，把两次遍历的过程分开：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int size = nums.size();
        vector<int> ret(size, -1);
        stack<int> st;
        for(int i = 0; i < size; i++) {
            while(!st.empty() && nums[st.top()] < nums[i]) {
                ret[st.top()] = nums[i];
                st.pop();
            }
            st.push(i % size);
        }
        for(int i = 0; i < size; i++) {
            while(!st.empty() && nums[st.top()] < nums[i]) {
                ret[st.top()] = nums[i];
                st.pop();
            }
        }
        return ret;
    }
};

556. Next Greater Element III

Analysis

题意很简单，给一个数，将这个数字的每一位重新组合形成一个新的数，在所有的这些新数中，找出比给定的数大且是这些数中最小的数（话都不会说了）。

Code

给的 n 的范围是 $[1, 2^{31} - 1]$，也就是最多不超过 10 位。10 个数字构成十位数，一共有 10! 种，这是极端情况下，一般是小于这个数的，因为可能存在重复的数字。
如果 dfs 搜索出所有结果，然后再选出符合条件的最小值，堆栈可能会爆。
换个角度理解，重新构造数字的过程，实际上也是每一位上的数字重新排列的过程。

首先思考一下什么样数字没有比它大的数？显然，数位上的数字是逆序排列的数字，比如：321、872 和 9991 等，这类数字已经是这些数字组合的最大排列了。
再来思考如何组成比给定数下一个大的数，下一个大换句话说，就是刚刚大、大了一点，也就是说，这个这个新数字与原数字是有部分相同的数位的，而且为了保证是“下一个大”，高位上的数字一定是相同的。
也就是说，需要从低位开始找。哪找什么样子的呢？按照前面的分析，如果是逆序排列的数字，不存在比它大的数。所以，要找的那个数字就是第一个不构成逆序的数字。还是举例子，比如 943765，倒数过来，第一个不构成逆序的数字就是 3。
找到第一个不构成逆序的数之后呢？同样为了保证“下一个大”，不能去动前面的数字，所以只能找后面的数来与这个数交换。实际上，我们可以很容易的看出 943765 的“下一个大”的数字就是 945367，也就是让 3 与其后面比它第一个大的 5 进行交换，然后再逆序得到的 763 这个序列。
按照这样的思路，就可以得到下一个大的数字了。

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        int len = s.length();
        if(len == 1) return -1;
        int pos = len - 2;
        while(pos >= 0 && s[pos] >= s[pos + 1]) pos--;
        if(pos < 0) return -1;
        int nextpost = len - 1;
        while(nextpost >= 0 && s[nextpost] <= s[pos]) nextpost--;
        swap(s[pos], s[nextpost]);
        reverse(s.begin() + pos + 1, s.end());
        long long ret = 0;
        for(int i = 0; i < len; i++) {
            ret = ret * 10 + s[i] - '0';
        }
        if(ret > INT_MAX) return -1;
        return ret;
    }
};

最后别忘记了，题目限定了数字的结果是 $[1, 2^{31} - 1]$ 的范围内。
另外，转换整数的过程可以调用库函数 stoll 完成：

1	long long ret = stoll(s);

31. Next Permutation

Analysis

顺路把这个题也解决了，好像与上面的题目是一样的。
读了一下题目，果然是一样的。解题的思路基本上是一致的，只是不需要在做 int 溢出判断了。

Code

em，思路完全一致...

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int size = nums.size();
        int pos = size - 2;
        while(pos >= 0 && nums[pos] >= nums[pos + 1]) pos--;
        if(pos == -1) {
            reverse(nums.begin(), nums.end());
        } else {
            int nextpos = size - 1;
            while(nextpos >= 0 && nums[nextpos] <= nums[pos]) nextpos--;
            swap(nums[pos], nums[nextpos]);
            reverse(nums.begin() + pos + 1, nums.end());
        }
    }
};

容易忽略的地方还有一点，那就是在寻找这两个数时，一定要严格大于或小于，不能等于。
实际上，C++ 内有现成的函数可以用😁。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};

Summary

不知道说什么好了...