LeetCode 632. Smallest Range Covering Elements from K Lists

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/description/

題目大意

你有 k 個有序的整數 lists ，這些 lists 中的數字皆呈不遞減
找出一個最小的範圍，使得該範圍至少包含每個 lists 中的一個數字

題目定義範圍 [a, b] 小於範圍 [c, d] 是當 b - a < d - c 或 b - a = d - c 的情況下 a < c

思考

Algo 1

我想了想覺得這題也是一樣可以用貪婪的策略去解：

class Solution
{
public:
    vector<int> smallestRange(vector<vector<int>> &nums)
    {
        auto comp = [&](const T &a, const T &b)
        {
            return a.data > b.data;
        };
        priority_queue<T, vector<T>, decltype(comp)> minHeap(comp);
        const int n = nums.size();
        int minVal = INT_MAX;
        int maxVal = INT_MIN;

        for (int i = 0; i < n; ++i)
        {
            const int num = nums[i][0];
            minHeap.emplace(i, 0, num);
            minVal = min(minVal, num);
            maxVal = max(maxVal, num);
        }

        int ansMin = minVal, ansMax = maxVal;

        while (minHeap.size() == n)
        {
            const auto [i, j, _] = minHeap.top();
            minHeap.pop();
            if (j + 1 < nums[i].size())
            {
                const int nextVal = nums[i][j + 1];
                minHeap.emplace(i, j + 1, nextVal);
                minVal = minHeap.top().data;
                maxVal = max(maxVal, nextVal);

                if (maxVal - minVal < ansMax - ansMin)
                {
                    ansMin = minVal;
                    ansMax = maxVal;
                }
            }
        }

        return {ansMin, ansMax};
    }

private:
    struct T
    {
        int i;
        int j;
        int data;

        T(int i, int j, int data) : i(i), j(j), data(data) {}
    };
};

Algo 2

或者你可以用 sliding windows 的方式去解
像是我改用 Go 寫的時候就改用這種方式去寫：

func smallestRange(nums [][]int) []int {
	valIdx := map[int][]int{}
	ans := []int{}

	for i, lst := range nums {
		for _, val := range lst {
			if _, exists := valIdx[val]; !exists {
				valIdx[val] = []int{}
				ans = append(ans, val)
			}
			valIdx[val] = append(valIdx[val], i)
		}
	}

	visCnt := map[int]int{}
	sort.Slice(ans, func(i int, j int) bool {
		return ans[i] < ans[j]
	})

	minS, minE, start, end := -1, -1, 0, 0

	for end < len(ans) {
		indices := valIdx[ans[end]]
		for _, v := range indices {
			visCnt[v]++
		}

		for len(visCnt) == len(nums) && start <= end {
			if minS == -1 || (ans[minE]-ans[minS] > ans[end]-ans[start]) {
				minS = start
				minE = end
			}

			startIdx := valIdx[ans[start]]
			for _, v := range startIdx {
				visCnt[v]--
				if visCnt[v] == 0 {
					delete(visCnt, v)
				}
			}
			start++
		}
		end++
	}

	return []int{ans[minS], ans[minE]}
}