Skip to content

632. Smallest Range

632. Smallest Range

题目: https://leetcode.com/problems/smallest-range/

难度: Hard

题意：

  1. 给定n个序列，求一个最小区间，使得每个序列至少一个数在这个区间里面

思路：

  • 采用移动区间的做法。如果区间左端点为l，那么我们需要在所有的序列中寻找比l大的最小数，构成一个区间[l, r]
  • 首先，将所有序列的第一个数字入堆，我们记录一个最大值。这时候堆里面的数形成一个区间，判断和记录下来。接着区间开始移动，将堆里面的最小数弹出丢掉，再从这个最小数所在的序列取出下一个数放进堆，又形成一个区间，判断和记录下来。如此循环，直到其中一个序列没有数可以进堆

解法：

class Solution {
public:
    struct myData {
        int x, y, value;
        myData(int _x = 0, int _y = 0, int _value = 0): x(_x), y(_y), value(_value) {}
        bool operator<(const myData &b) const {
            return value > b.value;
        }
    };
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int l = -10000000, r = -10000000;
        priority_queue<myData> q;
        int res = -10000000;
        for (int i = 0;i < nums.size();i++) {
            q.push(myData(i, 0, nums[i][0]));
            res = res > nums[i][0] ? res : nums[i][0];
        }
        while (q.size() == nums.size()) {            
            myData t = q.top();
            q.pop();
            if (l == -10000000 || (res - t.value) < (r - l)) {
                l = t.value;
                r = res;
            }
            if (t.y + 1 < nums[t.x].size()) {
                q.push(myData(t.x, t.y + 1, nums[t.x][t.y + 1]));
                res = res > nums[t.x][t.y + 1] ? res : nums[t.x][t.y + 1];
            }
        }
        vector<int> ret;
        ret.push_back(l);
        ret.push_back(r);
        return ret;
    }
};
回到顶部