牛牛在玩一个游戏，他操纵的游戏角色现在在一个坐标系的(0,0)处，他每次操纵该游戏角色都只能使它往上走或者往右走，向上走记为'U'，向右走记为'R'。在这个坐标系中散落着n张卡片，当该游戏角色移动到卡片的位置上时即可收集到这张卡片。
游戏胜利的条件是：收集到所有的卡片。
现在，牛牛想知道他能否赢得游戏，所以他想请聪明的你帮他写一个程序，如果可以赢得游戏，请返回移动的路径序列(例如："RURURUR")，如果不可以，请返回"NO"。当然，如果有多条路径都可以赢得游戏，请输出字典序最小的一条。

时间复杂度图片说明 空间复杂度 图片说明
解法：我们可以利用一个pair或者结构体存储卡片的坐标，然后进行排序，排序的x与y的优先级任意，因为下一张卡片一定在当前游戏角色位置右方/上方/右上方，否则直接输出NO，因为不可能存在这种移动方式。
在输出移动序列时，为了使字典序最小，所以能先用'R'就用'R'，因为'U'的字典序比'R'大。
按照上述思路进行模拟即可，我这里使用的pair，代码如下：

typedef pair<int, int> P;

string add(int up, int right, string ans)
{
    int i;
    for (i = 0; i < right; i++)
        ans += "R";
    for (i = 0; i < up; i++)
        ans += "U";
    return ans;
}
/**
 * 如果可以赢得游戏，返回字典序最小的序列，反之返回"NO"
 * @param n int整型 卡片的数量
 * @param a int整型vector<vector<>> 卡片的坐标数组
 * @return string字符串
 */
string solve(int n, vector<vector<int>> &a)
{
    // write code here
    int i;
    P p[10050]; //使用pair默认先x再y
    p[0] = P(0, 0);
    string ans = "";
    for (int i = 0; i < n; i++)
    {
        p[i + 1].first = a[i][0];
        p[i + 1].second = a[i][1];
    }
    sort(p + 1, p + 1 + n);
    for (i = 1; i <= n; i++)
    {
        if (p[i].first > p[i - 1].first && p[i].second < p[i - 1].second)
        {
            return "NO";
        }
        ans = add(p[i].second - p[i - 1].second, p[i].first - p[i - 1].first, ans);
    }
    return ans;
}

写法还可以优化，可以不开额外的数组，在string的尾部添加char，可以使用append。
由于只能向右和向上走，所以将坐标按x值排序，然后按y排成非递减的序列，如果不能排成则肯定不存在路径，然后就贪心地构造就行了，要构成字典序最小，所以先向右走，再向上走（‘R’<'U'）
时间复杂度图片说明 空间复杂度 图片说明

class Solution {
public:
    /**
     * 如果可以赢得游戏，返回字典序最小的序列，反之返回"NO"
     * @param n int整型 卡片的数量
     * @param a int整型vector<vector<>> 卡片的坐标数组
     * @return string字符串
     */
    string solve(int n, vector<vector<int> >& a) {
        // write code here
        a.push_back({ 0,0 });
        sort(a.begin(), a.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
            });
        string ret = "";
        int i = 0;
        for (i + 1; i + 1 < n && a[i+1] == vector<int>{0, 0}; i++);
        for (i++,n++; i < n; i++)
            if (a[i][1] < a[i-1][1])
                return "NO";
            else
            {
                ret.append(a[i][0] - a[i - 1][0], &#39;R&#39;);
                ret.append(a[i][1] - a[i - 1][1], &#39;U&#39;);
            }
        return ret;
    }
};

感谢审题人@张领统提供的另一份时间复杂度O(n),空间复杂度O(n)的解法：

class Solution
{
public:
    /**
     * 如果可以赢得游戏，返回字典序最小的序列，反之返回"NO"
     * @param n int整型 卡片的数量
     * @param a int整型vector<vector<>> 卡片的坐标数组
     * @return string字符串
     */
    string solve(int n, vector<vector<int>> &a)
    {
        vector<int> cnt(10005, 0);
        vector<int> mn(10005, 1e8);
        vector<int> mx(10005, -1);

        for (auto &p : a)
        {
            cnt[p[0]]++;
            mn[p[0]] = min(p[1], mn[p[0]]);
            mx[p[0]] = max(p[1], mx[p[0]]);
        }

        int prev = 0;
        int flag = 1;
        for (int i = 0; i < 10005; i++)
        {
            if (cnt[i] == 0)
                continue;
            if (mn[i] < prev)
            {
                flag = 0;
                break;
            }
            prev = mx[i];
        }

        if (!flag)
            return "NO";
        int prevx = 0, prevy = 0;
        string ans = "";
        for (int i = 0; i < 10005; i++)
        {
            if (cnt[i] == 0)
                continue;
            for (int j = prevx; j < i; j++)
                ans += &#39;R&#39;;
            for (int j = prevy; j < mx[i]; j++)
                ans += &#39;U&#39;;
            prevx = i;
            prevy = mx[i];
        }
        return ans;
    }
};