Leetcode 4.14

1.单词规律

首先需要把非空子串挨个提取出来；
其次需要维护两个unordered_map

• 如果stp不为空，且stp[s[i]] != p[i], string对应的字母不正确；
• 如果pts不为空，且pts[p[i]] != s[i], 字母对应的string不正确；

直接返回false。

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> st;
        stringstream iss(s);
        string word;
        while (iss>>word) st.push_back(word);

        if (st.size() != pattern.size()) return false;

        unordered_map<string, char> stp;
        unordered_map<char, string> pts;

        for (int i = 0; i < st.size(); i++) {
            if ((pts.count(pattern[i]) && pts[pattern[i]] != st[i]) || 
                (stp.count(st[i]) && stp[st[i]] != pattern[i]))
                return false;
            
            stp[st[i]] = pattern[i];
            pts[pattern[i]] = st[i];
        }
        return true;
    }
};

2.下一个更大元素 III

把 nnn 转换成字符串（字符数组），那么本题实际上是在求字符数组的 31. 下一个排列。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。

我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。

同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。

例如 2, 6, 3, 5, 4, 1 这个排列， 我们想要找到下一个刚好比他大的排列，于是可以从后往前看。
我们先看后两位 4, 1 能否组成更大的排列，答案是不可以，同理 5, 4, 1也不可以 直到3, 5, 4, 1这个排列，因为 3 < 5， 我们可以通过重新排列这一段数字，来得到下一个排列。
因为我们需要使得新的排列尽量小，所以我们从后往前找第一个比3更大的数字，发现是4
然后，我们调换3和4的位置，得到4, 5, 3, 1这个数列
因为我们需要使得新生成的数列尽量小，于是我们可以对5, 3, 1进行排序，可以发现在这个算法中，我们得到的末尾数字一定是倒序排列的，于是我们只需要把它反转即可
最终，我们得到了4, 1, 3, 5这个数列 完整的数列则是2, 6, 4, 1, 3, 5。

从后往前找第一个[i -1] < [i]，然后再从后往前找首个大于[i-1]的进行交换，再把[i]到[end]倒序。

class Solution {
public:
    int nextGreaterElement(int n) {
        //思路是，找到左边较小数和右边较大数交换
        //较小数尽可能靠左，较大数尽可能靠右
        int ans = -1;
        string nums = to_string(n);
        int i = nums.length() - 2;
        //从后往前，找到第一个前一个元素比后一个元素小的位置num[i]
        while (i >=0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        //没找到
        if (i < 0) {
            return -1;
        }

        //找end到i-1位置，第一个大于nums[i]的元素
        int j = nums.length() - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        swap(nums[i], nums[j]);
        reverse(nums.begin() + i + 1, nums.end());
        long res =  stol(nums);
        return res > INT_MAX ? -1 : res;
    }
};

3.