Maximum Distance Between a Pair of Values

给两个递减数组, 找到最远的逆序对儿.

这题因为是排序好的, 用二叉搜索找, 注意先翻转一下, 然后再用lower_bound. 而且还要减去当前i的不被考虑的情况.

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int res = 0;
        int n = nums1.size();
        int m = nums2.size();
        reverse(nums2.begin(), nums2.end());
        for(int i = 0; i < n; i++) {
            int f = lower_bound(nums2.begin(), nums2.end() - i, nums1[i]) - (nums2.begin());//[0, length - i]
            f = m - f - 1;
            res = max(res, f - i);
        }
        return res;
    }
};

class Solution {
public:
    string sortSentence(string s) {
        stringstream ss(s);
        string w;
        int n = 0;
        unordered_map<int, string> map;
        while(ss >> w){
            map[w.back() - '0'] = w.substr(0, w.length() - 1);
            n++;
        }
        stringstream so;
        for(int i = 1; i <= n; i++){
            so << map[i] << ' ';
        }
        string res = so.str();
        return res.substr(0, res.length() - 1);
    }
};