Cinte's Leetcode Record
0%

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

312. 戳气球

自上而下

戳气球会导致左右邻居的移动，因此将问题转化为添加气球

helper(i, j)表示在i~j这个开区间内添加气球，之所以开区间是因为左右区间设置为边界外，那里的气球是不能戳的，可以考虑到。

然后寻找这个区间添加后值最大的气球，对左右两边继续进行添加，对于每个区间，都会遍历每个值，然后对左右两边进行递归，从而求出

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 maxCoins(vector<int>& nums) {
        vector<int> val(nums.size() + 2, 1);
        vector<vector<int>> memo(nums.size() + 2, vector<int>(nums.size() + 2, -1));
        for(int i = 0; i < nums.size(); ++i)
            val[i + 1] = nums[i];
        return helper(0, nums.size() + 1, memo, val);
    }
private:
    int helper(int lo, int hi, vector<vector<int>>& memo, vector<int>& val)
    {
        if(lo >= hi - 1) // 注意这个，由于是开区间，所以当left和right相差1时，内部已经没有元素了，所以返回
            return 0;
        if(memo[lo][hi] != -1)
            return memo[lo][hi];
        for(int i = lo + 1; i < hi; ++i)
        {
            auto pro = val[lo] * val[i] * val[hi];
            pro += helper(lo, i, memo, val) + helper(i, hi, memo, val);
            memo[lo][hi] = max(memo[lo][hi], pro);
        }
        return memo[lo][hi];
    }
};
自下而上
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:
    int maxCoins(vector<int>& nums) {
        vector<int> val(nums.size() + 2, 1);
        vector<vector<int>> memo(nums.size() + 2, vector<int>(nums.size() + 2, 0));
        for(int i = 0; i < nums.size(); ++i)
            val[i + 1] = nums[i];
        // 从后面往前，小区间逐渐计算到大区间，之所以要从后往前，是因为如果从前往后的话，那就从大到校了
        for(int i = nums.size() - 1; i >= 0; --i)
        {
            // 从i + 2，开始，因为i和j间必须存在一个元素
            for(int j = i + 2; j < nums.size() + 2; ++j)
            {
                // 遍历
                for(int k = i + 1; k < j; ++k)
                {
                    auto pro = val[i] * val[k] * val[j];
                    // i ~ k 和 k ~ j都是在已经遍历过的区间内
                    // 由于k<j,所以memo[k]已经可以从之前的i，j遍历结果出来了，当没有元素时候就是0，是base，而k>i，所以memo[k][j]也可以从之前的结果出来了
                    pro += memo[i][k] + memo[k][j];
                    memo[i][j] = max(memo[i][j], pro);
                }
            }
        }
        return memo[0][nums.size() + 1]; // 返回最大区间的解
    }
};

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

301. 删除无效的括号

BackTrack
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        // 记录左右括号数，当碰到右括号时，若左括号数不为0，那么左括号数减一，表示这是一对合法括号，
        // 若左括号数为0，那么右括号数加一，这是一个需要删除的括号
        // 若遇到左括号，那么由于合法左括号不会出现在右括号之后，因此只需要左括号数加一即可
        // 剩下的左括号数和右括号数就是应当删除的括号数
        for(auto& ch : s)
        {
            if(ch == '(')
                ++leftCount;
            else if(ch == ')')
            {
                if(leftCount == 0)
                    ++rightCount;
                else
                    --leftCount;
            }
        }
        // 开始回溯
        string tmp = "";
        helper(s, 0, tmp, 0, 0);
        return ret;
    }
private:
    vector<string> ret;
    unordered_set<string> set;
    // 记录无效的左右括号数
    int leftCount = 0;
    int rightCount = 0;
private:
    void helper(string& s, int index, string& tmp, int curLeft, int curRight)
    {
        if(index == s.size())
        {
            // 当左括号和右括号全都删掉后，由于回溯过程中保证左括号小于右括号，所以此时必定为合法的。然后使用set去重
            if(set.emplace(tmp).second && leftCount == 0 && rightCount == 0) // 这种似乎会超时，需要用下面那种的写法
                ret.push_back(tmp);
            return;
        }

        if(s[index] == '(')
        {
            // 若左括号没有删除完
            if(leftCount != 0)
            {
                // 删除这个左括号，开始回溯
                --leftCount;
                helper(s, index + 1, tmp, curLeft, curRight);
                ++leftCount;
            }
            // 保留这个左括号，开始回溯
            tmp += '(';
            ++curLeft; // 当前的左括号数+1
            helper(s, index + 1, tmp, curLeft, curRight);
            --curLeft;
            tmp.pop_back();
        }else if(s[index] == ')')
        {
            // 只有目前遇到的左括号数>右括号数时，才可以选择删除这个右括号或者保留
            if(curLeft > curRight)
            {
                // 与左括号类似
                if(rightCount != 0)
                {
                    --rightCount;
                    helper(s, index + 1, tmp, curLeft, curRight);
                    ++rightCount;
                }
                tmp += ')';
                ++curRight;
                helper(s, index + 1, tmp, curLeft, curRight);
                --curRight;
                tmp.pop_back();
            // 当左括号数==右括号数时，只能抛弃这个右括号，不能保留，否则就是无效状态了
            }else if(curLeft == curRight)
            {
                --rightCount;
                helper(s, index + 1, tmp, curLeft, curRight);
                ++rightCount;
            }
        }else
        {
            // 碰到字母，就保留
            tmp += s[index];
            helper(s, index + 1, tmp, curLeft, curRight);
            tmp.pop_back();
        }
    }
};

精简优化,思路同上

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
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        for(auto& ch : s)
        {
            if(ch == ')')
            {
                if(leftCount == 0)
                    ++rightCount;
                else
                    --leftCount;
            }else if(ch == '(')
                ++leftCount;
        }
        string tmp;
        helper(s, 0, s.size(), 0, 0, tmp);
        vector<string> ret(set.begin(), set.end());
        return ret;
    }
private:
    unordered_set<string> set;
    int leftCount = 0;
    int rightCount = 0;
    void helper(string& s, int index, int sz, int curLeft, int curRight, string& tmp)
    {
        if(index == sz)
        {
            if(leftCount == 0 && rightCount == 0)
                set.insert(tmp);
            return;
        }
        auto ch = s[index];
        if(ch == '(' && leftCount)
        {
            --leftCount;
            helper(s, index + 1, sz, curLeft, curRight, tmp);
            ++leftCount;
        }else if(ch == ')' && rightCount)
        {
            --rightCount;
            helper(s, index + 1, sz, curLeft, curRight, tmp);
            ++rightCount;
        }
        tmp += ch;
        if(ch != ')' && ch != '(')
            helper(s, index + 1, sz, curLeft, curRight, tmp);
        else if(ch == ')' && curLeft > curRight)
            helper(s, index + 1, sz, curLeft, curRight + 1, tmp);
        else if(ch == '(')
            helper(s, index + 1, sz, curLeft + 1, curRight, tmp);
        tmp.pop_back();
    }
};
BFS

对于一串，每层把每个括号都删掉一次试试看，然后进入下一层，每层删掉的括号是一致的，当一层碰到有效后，把这一层所有有效的加入然后返回。

。。。。不想写（抄

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

145. 二叉树的后序遍历

迭代算法

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> ret;
        TreeNode* prev = nullptr; // 来判断右子树是否访问过，以免重复访问，关键
        while(!s.empty() || root)
        {
            // 先把左边全都压入栈
            while(root)
            {
                s.push(root);
                root = root->left; 
            }
            root = s.top(); // 弹出节点
            s.pop();
            // 如果节点右边为空，或者右边树之前走过了，那就轮到记录当前节点的值了
            if(!root->right || root->right == prev) 
            {
                ret.push_back(root->val);
                prev = root; // 这个节点走过了，如果没有设置这个的话，假设s是t的右节点，这里如果遍历s后，下一个弹出的就是t了，而t的右节点显然为s，但是非空，因此会进入else中继续进入右节点，导致无限循环。
                // 换言之，在弹出过程中，root是向上移动的，为了防止他重复进入，用prev堵住
                root = nullptr; // 这里都遍历到右边说明右边遍历完了，那么左边自然也遍历完了，防止他再进自己左边，就需要设为null，然后前面的都是进栈了
            }else
            {
                s.push(root); // 右边还有东西，重新压root入栈，走完右边再用
                root = root->right; // 进入右边
            }
        }
        return ret;
    }
};

递归算法

太简单不写了

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

144. 二叉树的前序遍历

迭代算法

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> q;
        vector<int> ret;
        while(!q.empty() || root)
        {
            while(root)
            {
                q.push(root);
                ret.push_back(root->val);
                root = root->left;
            }
            root = q.top();
            q.pop();
            root = root->right;
        }
        return ret;
    }
};

递归

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        tra(root);
        return ret;
    }
private:
    vector<int> ret;
    void tra(TreeNode* root)
    {
        if(!root)
            return;
        ret.push_back(root->val);
        tra(root->left);
        tra(root->right);
    }
};

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

309. 最佳买卖股票时机含冷冻期

dp

冷冻期的处理：如果前一天卖出股票，这一天就不能卖，如果前一天没卖，这一天就能卖或者不卖。

对于目前的持股状态，根据卖出和不卖出，持有和不持有组合，共有四种情况：

  1. 我现在有股票，并且当天没卖出
  2. 我现在有股票，并且当天卖出了 (违背事实，舍去)
  3. 我现在没股票，并且当天没卖出
  4. 我现在没股票，并且当天卖出了

对于1

​ 由于我现在有并且当天没卖出，所以当天的值就是前一天1情况或者前一天没股票但是买入了，也就是3+今天买入后(冷冻期)

对于3

​ 由于我现在没有而且当天也没有，说明我之前就没有，今天也不能买过来，所以我今天的收益就是3和4之中的最大值

对于4

​ 由于我现在没有并且当天卖出了，则今天就不能买入了，所以前一天不能卖出，所以值就是前一天1的情况加上今天卖出的收益。

以上三种状态同步进行，最后最大值会在3，4之间获得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(3));
        dp[0][0] = -prices[0]; // 有股票而且当天没卖出，对应1
        dp[0][1] = 0; // 没股票并且当天没卖出，对应3
        dp[0][2] = 0; // 有股票但当天卖了，对应4，视为0

        for(int i = 1; i < prices.size(); ++i)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return max(dp.back()[1], dp.back()[2]);
    }
};

发现只用到了前一天的数据，所以可以把S(n)优化为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp[3]{-prices[0], 0, 0};
        for(int i = 1; i < prices.size(); ++i)
        {
            auto tmp = dp[2];
            dp[2] = dp[0] + prices[i];
            dp[0] = max(dp[0], dp[1] - prices[i]);
            dp[1] = max(dp[1], tmp);
        }
        return max(dp[1], dp[2]);
    }
};
review

根据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int m = prices.size();
        if(m == 1)
            return 0;
        vector<int> have(m);
        vector<int> notHave(m);
        have[0] = -prices[0];
        notHave[0] = 0;
        have[1] = max(-prices[1], -prices[0]);
        notHave[1] = max(0, -prices[0] + prices[1]);
        for(int i = 2; i < m; ++i)
        {
            have[i] = max(notHave[i - 2] - prices[i], have[i - 1]);
            notHave[i] = max(have[i - 1] + prices[i], notHave[i - 1]);
        }
        return notHave.back();
    }
};

优化空间后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int m = prices.size();
        int have[2]{ 0, -prices[0] };
        int notHave[2]{ 0, 0 };
        for(int i = 1; i < m; ++i)
        {
            have[0] = max(notHave[0] - prices[i], have[1]);
            notHave[0] = max(have[1] + prices[i], notHave[1]);
            swap(have[0], have[1]);
            swap(notHave[0], notHave[1]);
        }
        return notHave[1];
    }
};

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

438. Find All Anagrams in a String

sliding window大佬归纳

滑动窗口
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> findAnagrams(string s, string p) {
        unordered_map<char, int> map;
        for(auto ch : p)
            ++map[ch];
        int count = map.size();
        vector<int> ret;
        int begin = 0, end = 0, n = s.size(), m = p.size();
        while(end < n)
        {
            if(map.count(s[end]) && --map[s[end]] == 0)
                --count;
            while(count == 0)
            {
                if(end - begin + 1 == m)
                    ret.push_back(begin);
                if(map.count(s[begin]) && ++map[s[begin]] > 0)
                    ++count;
                ++begin;
            }
            ++end;
        }
        return ret;

    }
};

review

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> findAnagrams(string s, string p) {
        unordered_map<char, int> map;
        for(auto ch : p)
            ++map[ch];
        int count = map.size();
        vector<int> ret;
        int begin = 0, end = 0, n = s.size(), m = p.size();
        while(end < n)
        {
            if(--map[s[end]] == 0) // 如果s[end]不在map中，减的结果会是小于0，不会影响count的计数，而且这个map中减去的最后会随着窗口滑动而重新归零
                --count;
            while(count == 0)
            {
                if(end - begin + 1 == m) // count是0了，且长度符合，所以是解
                    ret.push_back(begin);
                if(++map[s[begin++]] > 0) // 这里没有判定s[begin]是不是在map中，如果不在count中，随着窗口的滑动，他顶多归零，不会影响到count
                    ++count;
            }
            ++end;
        }
        return ret;

    }
};

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

399. 除法求值

直接看解析

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
69
70
71
72
73
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, int> map;
        UnionFind uf(equations.size() * 2);
        int id = 0;
        for(int i = 0; i < equations.size(); ++i)
        {
            auto a = equations[i][0];
            auto b = equations[i][1];
            if(map.emplace(a, id).second)
                ++id;
            if(map.emplace(b, id).second)
                ++id;
            
            uf.doUnion(map[a], map[b], values[i]);
        }
        vector<double> ret;
        for(auto& query : queries)
        {
            if(map.find(query[0]) != map.end() && map.find(query[1]) != map.end())
                // map如果其中不包含值会初始化为0，因此这里需要先判断
                ret.push_back(uf.isConnect(map[query[0]], map[query[1]]));
            else
                ret.push_back(-1.0);
        }
        return ret;
    }
private:
    class UnionFind {
        public:
            UnionFind(int size) : parent(vector<int>(size)), weights(vector<double>(size, 1.0))
            {
                for(int i = 0; i < size; ++i)
                    parent[i] = i;
            }
			// 归并，如果已经连接了，那就算了，如果没有连接，由于他们出现在同一式中，因此必定可以建立连接。如果他们的根没有连接那就计算一下然后连接，在find操作时会执行路径压缩
            void doUnion(int x, int y, double val)
            {
                int rootX = find(x);
                int rootY = find(y);
                if(rootX == rootY)
                    return;
                parent[rootX] = rootY;
                weights[rootX] = weights[y] * val / weights[x];
            }
			// 如果连在同一个父节点就是有值
            double isConnect(int x, int y)
            {
                int rootX = find(x);
                int rootY = find(y);
                if(rootX == rootY)
                    return weights[x] / weights[y];
                else
                    return -1.0;
            }
        private:
            vector<int> parent;
            vector<double> weights;
        private:
        	// 寻找父节点顺便路径压缩
            int find(int x)
            {
                if(x != parent[x])
                {
                    int ori = parent[x];
                    parent[x] = find(parent[x]);
                    weights[x] *= weights[ori];
                }
                return parent[x];
            }
    };
};

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

538. 把二叉搜索树转换为累加树

中序遍历变种
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int rightVal = 0;
        dfs(root, rightVal);
        return root;
    }
private:
    void dfs(TreeNode* root, int& rightVal)
    {
        if(!root)
            return;
        if(root->right)
        {
            dfs(root->right, rightVal);
        }
        root->val += rightVal;
        rightVal = root->val;
        if(root->left)
        {
            dfs(root->left, rightVal);
        }
    }
};

右->中->左

rightVal始终保存他右边树枝的最大值

我好傻

简单的思考方法:

中序单增，于是反中序为单减，对于每个节点加上他左边的和就行

迭代

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        stack<TreeNode*> q;
        int curSum = 0;
        TreeNode* ret = root;
        while(!q.empty() || root)
        {
            while(root)
            {
                q.push(root);
                root = root->right;
            }
            root = q.top();
            q.pop();
            curSum += root->val;
            root->val = curSum;
            root = root->left;
        }
        return ret;
    }
};

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

461. 汉明距离

直接移位
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hammingDistance(int x, int y) {
        x ^= y;
        int ret = 0;
        while(x)
        {
            ret += x & 1;
            x >>= 1;
        }
        return ret;
    }
};
只遍历1
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hammingDistance(int x, int y) {
        x ^= y;
        int ret = 0;
        while(x)
        {
            x &= x - 1;
            ++ret;
        }
        return ret;
    }
};

x-1会将x中最近的一个1变成0，而这个1左边的全变成1。

所以x&x-1会使得这个最近的1及其右边全都变成0，而左边保持不变，则每次都如此操作，循环次数就是1的个数

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

378. Kth Smallest Element in a Sorted Matrix

使用堆（只应用了行递增而没有用列递增）

对于矩阵

借助归并排序思想，把每一行视为一个递增序列，如果归并的话，就是把每一行归并序列合并为一个递增序列，但这题并不需要实现完整的操作

1
2
3
1  5   9
10 11 13
12 13 15

可以先窥探第一列，第一列是每一个行序列的最小值所组成的，因此第一列中的最小值毫无疑问是1，这里可以先弹出1，矩阵变为

1
2
3
   5  9
10 11 13
12 13 15

若要继续判断，只需要判断5, 10, 12中的最小值，然后继续弹出最小值

1
2
3
      9
10 11 13
12 13 15
1
2
3
       
10 11 13
12 13 15
1
2
3
   
   11 13
12 13 15

所以需要一个优先级队列来维护顶头最小，下面最大的一个堆，并且每个堆中的元素需要记录这个元素在矩阵中的坐标，从而可以在弹出后用它右边的元素接替。

代码如下：

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
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<Ele, vector<Ele>, less<Ele>> pq;
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; ++i)
            pq.push(Ele(matrix[i][0], i, 0));
        for(int i = 0; i < k - 1; ++i)
        {
            auto p = pq.top();
            pq.pop();
            if(p.y == n - 1)
                continue;
            pq.push(Ele(matrix[p.x][p.y + 1], p.x, p.y + 1));
        }
        return pq.top().val;
    }
private:
    struct Ele {
        int val;
        int x;
        int y;
        Ele(int val, int x, int y) : val(val), x(x), y(y) {}
        bool operator < (const Ele& ele) const
        {
            return this->val > ele.val;
        }
    };
};
1626163371546.png

less：当左边小于右边时，return true

priority_queue：当新进来的数导致了顺序错误，则return true。此处是新进来的数如果大于顶头的数，就return true。

因此类中应当重载<操作符，当左边小于右边时return false，也就是左边大于右边时return true。

lhs < rhs时，调用的是lhs的重载操作符，所以需要lhs>rhs返回true，所以是this->val>ele.val。

使用二分查找
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
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int lo = matrix[0][0], hi = matrix.back().back();
        while(lo < hi)
        {
            auto mid = (hi + lo) >> 1;
            auto num = check(matrix, mid);
            // 如果使用num == k时候就返回，就会导致mid可能不是这区间里数
            if(num >= k)
                hi = mid;
            else if(num < k)
                lo = mid + 1;
        }
        return hi;
    }
private:
    int check(vector<vector<int>>& matrix, int mid)
    {
        int i = matrix.size() - 1;
        int j = 0;
        int num = 0;
        while(i >= 0 && j < matrix[0].size())
        {
            if(matrix[i][j] <= mid) // =mid时候要算入，因为需要的是他是第几个，而不是比他小的有几个
            {
                ++j;
                num += i + 1;
            }else
            {
                --i;
            }
        }
        return num;
    }
};
怎么保证最后的值是矩阵中的值?

当lo和hi相遇时，他们肯定收敛一个矩阵中具有的数值

若right不在矩阵中

  1. 当mid恰好大于解一点点的话，最终得到的面积会与k相等，解位于lo~mid内，这时候令hi=mid
  2. 当mid恰好小于解一点点的话，最终得到的面积会小于k，这时候hi不变，lo变为mid+1，为什么lo不是mid呢，因为当取lo==mid时，由于c++中除法向下取整，所以会导致无限循环。而hi如果取mid-1，就会导致区间将不再包括hi。而lo取mid+1则不会，因为这种情况下mid+1~hi中肯定有解。

如果right在矩阵中

​ 与上述类似

所以，根据上述情况，解可以始终保证位于区间lo~hi之中，当lo和hi相等之时，就可以保证他们必定为解。