Mind palace

some thoughts

0%

Posted on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

O(mn) time
基本思路是先标记每行以及每列连续三个相同的candy，然后对每一列从下往上进行更新，最后反复更新board直到没有再需要调整的candy为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
        int R = board.size(), C = board[0].size();
        bool changed = false;
        // 横向只要是3个相同就变成负数
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c + 2 < C; ++c) {
                int v = abs(board[r][c]);
                if (v != 0 && v == abs(board[r][c + 1]) && v == abs(board[r][c + 2])) {
                    board[r][c] = board[r][c + 1] = board[r][c + 2] = -v;
                    changed = true;
                }
            }
        }
        // 纵向只要是3个相同就变成负数
        for (int r = 0; r + 2 < R; ++r) {
            for (int c = 0; c < C; ++c) {
                int v = abs(board[r][c]);
                if (v != 0 && v == abs(board[r + 1][c]) && v == abs(board[r + 2][c])) {
                    board[r][c] = board[r + 1][c] = board[r + 2][c] = -v;
                    changed = true;
                }
            }
        }
        if (!changed) return board;
        // 对于每一列从底往上移动
        for (int c = 0; c < C; ++c) {
            int i = R - 1; // 定义一个i表示当前要修改的元素
            for (int r = R - 1; r >= 0; --r) {
                if (board[r][c] > 0) {
                    board[i--][c] = board[r][c];
                }
            }
            for (; i >= 0; --i) { // 剩余元素全部置0
                board[i][c] = 0;
            }
        }
        return candyCrush(board);
    }
};

Posted on In Disqus:
Symbols count in article: 5.3k Reading time ≈ 5 mins.

decreasing stack + dp O(nd) time O(n) space
f[i]表示经过day天后截至jobDifficulty[i]的最小困难结果，即f[day][i]
因为f[day][i] = min{f[day - 1][j] + max{jobDifficulty[j + 1 : i]}}，假设jobDifficulty[j]是jobDifficulty[i]左边第一个更大的数，则max{jobDifficulty[j + 1 : i]} = jobDifficulty[i]
f[day][i] = min{f[day][j], min{f[day - 1][j + 1 : i - 1]} + jobDifficulty[i]}
因为jobDifficulty[j] > jobDifficulty[i]，所以f[day][j]的最后一个区间一定也可以cover整个jobDifficulty[j + 1 : i]区间，且根据归纳法f[day][j]一定不会比f[day - 1][j] + jobDifficulty[i]更差
找jobDifficulty[j]左边第一个更大的jobDifficulty[i]可以用单调栈，求min{f[day - 1][j + 1 : i - 1]}可以利用单调栈顺便保存每个小区间的前一天的最小困难结果，具体而言，如果单调栈所存下标为 k1,k2,…,kn，则在 k1的位置上额外存储区间[0, k1)的最小值，在k2的位置上额外存储区间[k1, k2)的最小值，以此类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<int> f(n);
        f[0] = jobDifficulty[0];
        for (int i = 1; i < n; ++i) {
            f[i] = max(f[i - 1], jobDifficulty[i]); // 先算出第一天后的结果
        }
        vector<int> t(n);
        for (int day = 1; day < d; ++day) { // d是1-based改成0-based
            swap(t, f);
            stack<pair<int, int>> s; // <区间最小困难结果，下标>
            for (int i = day; i < n; ++i) {
                int p = t[i - 1]; // 初始化为前一天截至jobDifficulty[i - 1]的最小困难结果
                while (!empty(s) && jobDifficulty[s.top().second] <= jobDifficulty[i]) {
                    p = min(p, s.top().first); // 用前一天前一个区间的最小困难结果来更新
                    s.pop();
                }
                if (empty(s)) {
                    f[i] = p + jobDifficulty[i]; // min{f[day - 1][0 : i - 1]} + jobDifficulty[i]
                } else {
                    f[i] = min(p + jobDifficulty[i], f[s.top().second]); // min{f[day][j], min{f[day - 1][j + 1 : i - 1]} + jobDifficulty[i]}
                }
                s.emplace(p, i);
            }
        }
        return f[n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<int> f(n);
        f[0] = jobDifficulty[0];
        for (int i = 1; i < n; ++i) {
            f[i] = max(f[i - 1], jobDifficulty[i]);
        }
        vector<int> t(f);
        for (int day = 1; day < d; ++day) {
            swap(t, f);
            vector<array<int, 3>> s{{M, M, M}};
            for (int i = day; i < n; ++i) {
                int p = t[i - 1];
                while (s.back()[1] <= jobDifficulty[i]) {
                    p = min(p, s.back()[0]);
                    s.pop_back();
                }
                s.push_back({p, jobDifficulty[i], min(p + jobDifficulty[i], s.back()[2])});
                f[i] = s.back()[2];
            }
        }
        return f[n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<int> f(n, M), t(n);
        for (int day = 0; day < d; ++day) {
            swap(t, f);
            stack<int> s;
            for (int i = day; i < n; ++i) {
                f[i] = i > 0 ? t[i - 1] + jobDifficulty[i] : jobDifficulty[i];
                while (!empty(s) && jobDifficulty[s.top()] <= jobDifficulty[i]) {
                    f[i] = min(f[i], f[s.top()] - jobDifficulty[s.top()] + jobDifficulty[i]);
                    s.pop();
                }
                if (!empty(s)) {
                    f[i] = min(f[i], f[s.top()]);
                }
                s.push(i);
            }
        }
        return f[n - 1];
    }
};

bottom-up dp O(nnd) time O(nd) space
f[day][i]表示到第day天安排前i个job的最小难度
转移方程为
f[day][i] = min{f[day - 1][j] + max{jobDifficulty[j : i - 1]}} where j ~ [day - 1, i - 1]
初始化
f[0][0] = 0表示到第0天安排前0个job的最小难度为0
其他都为inf，在之后的计算过程中凡是有f[day][i] where i < day的理论上都应该为inf
最终结果
f[d][n]
计算顺序
从前往后扫每天day，对于每天day，从前往后遍历每个i，再对每个i从后往前尝试每个j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<vector<int>> f(d + 1, vector<int>(n + 1, M));
        f[0][0] = 0;
        for (int day = 1; day <= d; ++day) {
            for (int i = day; i <= n; ++i) {
                int mx = INT_MIN;
                for (int j = i - 1; j >= day - 1; --j) { // j >= 0也可以但是实际上应该是j >= day - 1因为不可能出现比day - 1更小的j
                    mx = max(mx, jobDifficulty[j]);
                    f[day][i] = min(f[day][i], f[day - 1][j] + mx);
                }
            }
        }
        return f[d][n];
    }
};

rolling array优化
O(nnd) time O(n) space
需要注意的是计算每个f[day][i]之前必须要重置为inf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<vector<int>> f(2, vector<int>(n + 1, M));
        f[0][0] = 0;
        for (int day = 1; day <= d; ++day) {
            int dd = day & 1;
            for (int i = day; i <= n; ++i) {
                int mx = INT_MIN;
                f[dd][i] = M;
                for (int j = i - 1; j >= day - 1; --j) {
                    mx = max(mx, jobDifficulty[j]);
                    f[dd][i] = min(f[dd][i], f[dd ^ 1][j] + mx);
                }
            }
        }
        return f[d & 1][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<vector<int>> f(2, vector<int>(n + 1, M));
        f[0][0] = 0;
        for (int day = 1; day <= d; ++day) {
            for (int i = day; i <= n; ++i) {
                int mx = INT_MIN;
                f[day & 1][i] = M;
                for (int j = i - 1; j >= day - 1; --j) {
                    mx = max(mx, jobDifficulty[j]);
                    f[day & 1][i] = min(f[day & 1][i], f[(day - 1) & 1][j] + mx);
                }
            }
        }
        return f[d & 1][n];
    }
};

一维数组优化
O(nnd) time O(n) space
注意到每一行只跟前一行有关，对于每天day，可以改成从后往前遍历每个i，再对每个i从后往前尝试每个j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<int> f(n + 1, M);
        f[0] = 0;
        for (int day = 1; day <= d; ++day) {
            for (int i = n; i >= day; --i) {
                f[i] = M;
                int mx = INT_MIN;
                for (int j = i - 1; j >= day - 1; --j) {
                    mx = max(mx, jobDifficulty[j]);
                    f[i] = min(f[i], f[j] + mx);
                }
            }
        }
        return f[n];
    }
};

Posted on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

O(n) time
判断是否能在一个circle里：

  1. 跑一遍所有instructions之后能回到原点
  2. 即使不能回到原点，但是最后的方向跟初始不一样（只要方向不一样，跑两遍或者四遍还是回到原点）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isRobotBounded(string instructions) {
        int x = 0, y = 0, i = 0, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // 方向顺序NESW
        for (char c : instructions) {
            switch (c) {
                case 'L': i = (i + 3) % 4; break; // 左拐等于右拐三次
                case 'R': i = (i + 1) % 4; break;
                default: x += dx[i]; y += dy[i]; break;
            }
        }
        return x == 0 && y == 0 || i > 0;
    }
};
Read more »

Posted on In Disqus:
Symbols count in article: 430 Reading time ≈ 1 mins.

O(mlogm + nlogn) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        return f(h, horizontalCuts) * f(w, verticalCuts) % int(1e9 + 7);
    }

    long f(int sz, vector<int> &A) {
        A.push_back(sz);
        A.push_back(0);
        sort(begin(A), end(A));
        int res = 0;
        for (int i = 1; i < size(A); ++i) {
            res = max(res, A[i] - A[i - 1]);
        }
        return res;
    }
};

Posted on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

dfs O(32) time O(16) space
generic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int pathSum(vector<int>& nums) {
        unordered_map<int, int> t;
        for (int x : nums) {
            t[x / 10] = x % 10; // 利用现有父子关系
        }
        dfs(t, 11, 0);
        return res;
    }

    void dfs(unordered_map<int, int> &t, int i, int s) {
        if (!t.count(i)) return;
        s += t[i];
        int r = i + 10 + i % 10, l = r - 1; // 33->45和46即33->43然后43+3得到46再-1得到45
        if (!t.count(l) && !t.count(r)) {
            res += s;
            return;
        }
        dfs(t, l, s);
        dfs(t, r, s);
    }

    int res = 0;
};
Read more »

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

问题：
在使用hexo写文章时，如果文章的title中包含双引号”abc”、$符号时会编译出错，文章无法渲染。
由于这里的写法是yml语法，”、$这些都是特殊符号，执行hexo -s时到编译title这里就会出现错误

1
2
3
---
title: Shell中$i $() ${}的区别
---

解决办法
这里我们需要对特殊符号进行转义，用对应的THML字符实体进行替换，例如$对应$，如此等等。
转移之后的标题就变成了

1
2
3
---
title: Shell中\&#36;i \&#36;&#40;&#41; \&#36;&#123;&#125;的区别
---

附录：各种常用特殊字符对应的HTML字符实体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
! &#33; — 惊叹号 Exclamation mark
" &#34; &quot; — 双引号 Quotation mark
# &#35; — 数字标志 Number sign
$ &#36; — 美元标志 Dollar sign
% &#37; — 百分号 Percent sign
& &#38; &amp; — 与符号(&) Ampersand
' &#39; — 单引号 Apostrophe
( &#40; — 小括号左边部分 Left parenthesis
) &#41; — 小括号右边部分 Right parenthesis
* &#42; — 星号 Asterisk
+ &#43; — 加号 Plus sign
< &#60; &lt; 小于号 Less than
= &#61; — 等于符号 Equals sign
- &#45; &minus; — 减号
> &#62; &gt; — 大于号 Greater than
? &#63; — 问号 Question mark
@ &#64; — Commercial at
[ &#91; — 中括号左边部分 Left square bracket
\ &#92; — 反斜杠 Reverse solidus (backslash)
] &#93; — 中括号右边部分 Right square bracket
{ &#123; — 大括号左边部分 Left curly brace
| &#124; — 竖线Vertical bar
} &#125; — 大括号右边部分 Right curly brace
空格 &nbsp;

Posted on Edited on In Disqus:
Symbols count in article: 4.2k Reading time ≈ 4 mins.

list是bidirectional iterator支持++和–

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class AllOne {
public:
    /** Initialize your data structure here. */
    AllOne() {

    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if (key2bucket.count(key) == 0) {
            key2bucket[key] = buckets.insert(buckets.end(), {0, {key}}); // 找不到『旧bucket』就先插一个
        }
        auto curr = key2bucket[key], prev = std::prev(curr);
        if (curr == buckets.begin() || prev->value > curr->value + 1) {
            prev = buckets.insert(curr, {curr->value + 1, {}}); // 如果没有『新bucket』就插一个
        }
        prev->keys.insert(key); // 从旧bucket挪到新bucket
        curr->keys.erase(key);
        if (curr->keys.empty()) {
            buckets.erase(curr);
        }
        key2bucket[key] = prev;
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if (key2bucket.count(key) == 0) return;
        auto curr = key2bucket[key], next = std::next(curr);
        key2bucket.erase(key); // 先删key反正后边要不删了就删了要不写新key
        if (curr->value != 1) {
            if (next == buckets.end() || curr->value - 1 > next->value) {
                next = buckets.insert(next, {curr->value - 1, {}}); // 如果没有『新bucket』加一个
            }
            next->keys.insert(key); // 从旧bucket挪到新bucket
            key2bucket[key] = next;
        }
        curr->keys.erase(key);
        if (curr->keys.empty()) {
            buckets.erase(curr);
        }
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return buckets.empty() ? "" : *begin(buckets.front().keys);
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return buckets.empty() ? "" : *begin(buckets.back().keys);
    }

    struct Bucket {
        int value = 0;
        unordered_set<string> keys;
    };
    unordered_map<string, list<Bucket>::iterator> key2bucket;
    list<Bucket> buckets;
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * string param_3 = obj.getMaxKey();
 * string param_4 = obj.getMinKey();
 */
Read more »

Posted on Edited on In Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

O(n2) time O(n2) space
因为stones[0]是0且初始步长是0所以步长最多为n也就是最多n种，所以对于每个stones[i]步长最多n种，复杂度O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool canCross(vector<int>& stones) {
        for (int i = 0, limit = 0; i < stones.size(); ++i) { // 可有可无，只是一个优化，假设前面每一跳都比前面一跳加1，那么到第i跳之后应该到 i * (i  + 1) / 2，假如stones[i]比这个要远，则意味着永远到不了stones[i]
            limit += i;
            if (stones[i] > limit) return false;
        }
        return canCross(stones, 0, 0);
    }

    bool canCross(const vector<int> &stones, int b, int k) { // 上一步步长为k达到的stones[b]，从b + 1开始遍历看[k - 1, k + 1]步长之内能到哪些stones
        int n = stones.size();
        if (b == n - 1) return true;
        auto key = (k << 11) | b; // 如果是全部integer则要用long key = (k << 32) | b;
        if (m.count(key)) return m[key];
        for (int i = b + 1; i < n; ++i) { // 这个循环实际上只需要遍历最多三个stones
            int jump = stones[i] - stones[b];
            if (jump < k - 1) continue;
            if (jump > k + 1) break;
            if (canCross(stones, i, jump)) return m[key] = true;
        }
        return m[key] = false;
    }

    unordered_map<int, bool> m; // 每个石头的下标+尝试到达stones[i]所需要的步长 和 用这个步长是否能到达stones[i]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool canCross(vector<int>& stones) {
        n = stones.size();
        for (int i = 0; i < n; ++i) {
            dict[stones[i]] = i;
        }
        return canCross(stones, 0, 1);
    }

    bool canCross(const vector<int> &stones, int b, int k) {
        if (k <= 0) return false;
        if (b == n - 1) return true;
        auto key = (k << 11) | b;
        if (m.count(key)) return m[key];
        int next = stones[b] + k;
        if (dict.count(next) == 0) return false;
        for (int d = -1; d <= 1; ++d) {
            if (canCross(stones, dict[next], k + d)) return m[key] = true;
        }
        return m[key] = false;
    }

    int n;
    unordered_map<int, int> m, dict;
};

O(n2) time O(n2) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> m; // 每个石头的位置stones[i]和到stones[i]有可能的步长
        for (int s : stones) {
            m[s] = {}; // 这一步必须要有，否则无法判断是否存在指定位置的石头
        }
        m[stones[0]].insert(0);
        for (int s : stones) {
            for (int k : m[s]) { // 每个石头最多只可能继承n种步长（否则就到最后一个了）所以内循环复杂度上限是O(n)
                for (int d = -1; d <= 1; ++d) {
                    int t = s + k + d;
                    if (t == stones.back()) return true;
                    if (k + d > 0 && m.count(t)) {
                        m[t].insert(k + d);
                    }
                }
            }
        }
        return false;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int cnt = 0;
        for (int x : data) {
            if (cnt == 0) { // cnt为0说明开始检查一个新的字符，先检查高8位
                if ((x >> 5) == 0b110) {
                    cnt = 1; // 对『每一个新的字符』初始化cnt
                } else if ((x >> 4) == 0b1110) {
                    cnt = 2;
                } else if ((x >> 3) == 0b11110) {
                    cnt = 3;
                } else if (x >> 7) return false;
            } else { // 再检查低8位
                if ((x >> 6) != 0b10) return false;
                --cnt; // 更新cnt
            }
        }
        return cnt == 0; // 最后cnt必须为0
    }
};
Read more »

Posted on Edited on In Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

multimap O(nlogk)
把heap换成multimap更直观，multimap里存的最小值和最大值就是当前可能的备选范围，不断减小最大值来得到新的最大值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        multimap<int, int, greater<int>> m;
        int k = nums.size();
        for (int i = 0; i < k; ++i) {
            m.emplace(nums[i].back(), i);
            nums[i].pop_back();
        }
        vector<int> res{-100000, 100000};
        while (!m.empty()) {
            auto h = begin(m);
            auto l = rbegin(m);
            auto [hi, i] = *h;
            auto [lo, _] = *l;
            if (hi - lo <= res[1] - res[0]) {
                res = {lo, hi};
            }
            m.erase(h);
            if (nums[i].empty()) break;
            m.emplace(nums[i].back(), i);
            nums[i].pop_back();
        }
        return res;
    }
};

max heap O(nlogk) n是数的个数，k是数组个数，这里用最大堆是想让每个数组从后往前剔除元素，避免维护指针麻烦
题目解法和merge k sorted lists类似，上来先取每个数组的最大值放入堆，并维护一个全局最小值，然后不停从堆顶元素对应的数组取数并更新堆顶、全局最小值和最大值直到某个数组为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        using pii = pair<int, int>;
        priority_queue<pii, vector<pii>> q;
        int k = nums.size();
        int lo = INT_MAX, hi = INT_MIN;
        for (int i = 0; i < k; ++i) {
            lo = min(lo, nums[i].back());
            hi = max(hi, nums[i].back());
            q.emplace(nums[i].back(), i);
            nums[i].pop_back();
        }
        vector<int> res{lo, hi};
        while (!q.empty()) {
            auto [hi, i] = q.top(); q.pop();
            if (hi - lo <= res[1] - res[0]) { // 因为是有序的，所以不需要单独考虑差系统的情况，但是必须要用小于等于，因为是从大到小遍历的，所以后边有可能有差相同但是range开端更小的来overwrite结果
                res = {lo, hi};
            }
            if (nums[i].empty()) break;
            lo = min(lo, nums[i].back());
            q.emplace(nums[i].back(), i);
            nums[i].pop_back();
        }
        return res;
    }
};

greedy+sliding window O(nlogn + n) time O(n) space
题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<pair<int, int>> ordered; // (number, group)
        for (int k = 0; k < nums.size(); ++k) {
            for (int x : nums[k]) {
                ordered.emplace_back(x, k);
            }
        }
        sort(ordered.begin(), ordered.end());
        int i = 0, k = size(nums);
        vector<int> res{-100000, 100000};
        unordered_map<int, int> count;
        for (int l = 0, r = 0; r < ordered.size(); ++r) {
            ++count[ordered[r].second];
            if (size(count) == k) {
                while (count[ordered[l].second] > 1) {
                    --count[ordered[l++].second];
                }
                if (ordered[r].first - ordered[l].first < res[1] - res[0]) {
                    res = {ordered[l].first, ordered[r].first};
                }
            }
        }

        return res;
    }
};