Title source

• leetcode：632. Minimum range

Title Description

class Solution {
    
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
    

    }
};

title

Analyze the data

• This is a two-dimensional array , The maximum length of a two-dimensional array is 3500; The length of one-dimensional array inside is the largest 50; If you look at every number , need 3500 * 50 = 175000 = 10^5.maybe Row column correspondence model ？？？

• The data range is quite large , Row column correspondence model pass
  
• It can be seen from the following , Monotonicity , Can we take advantage of this monotonicity ？ Two points ？ Monotonic stack ？ The sliding window ？

Analyze the meaning of the question

• Ask to choose an interval , In this range, at least one number falls on each dimension , And it requires the narrowest interval
• There may be more than one narrowest range , Choose the one with the lowest starting value

That is to say, the minimum interval , The following two points must be met ：

• Narrowest length （ first ）
• The starting point is the smallest when the length is the same

reflection

• How to ensure the narrowest length ？
  • This must be calculated in the process of checking
  • In order to make the interval narrowest , So the left and right endpoints of the interval should just cover a number of the array
  • In order to make the interval cover all arrays , So the left and right endpoints of the interval should be the maximum and minimum values in a column {min,max}
• Then how to ensure the minimum starting range ？
  • Each time will be The smallest element in the current interval is discarded , Replace with the next element in its original array
  • That is to say , If the elements we currently select from each interval are a1_1,a2_1,a3_1…ak_1 ( The first number represents the number from the array , The following number means that the number is the number of elements of the array ), If the smallest element at this time is ai_1, The biggest element is aj_1 , Then the interval is [ai_1, aj_1], The smallest element in the interval is ai_1, Then we will ai_1 discarded , take ai_2 Take it out and put it in .
  • reason ：
    • If you don't change ai_1, Then the starting point of the interval is always ai_1, And the length of the interval cannot be reduced , The length of the interval depends on the start and end points , And the end is impossible to get smaller .
    • Because we choose elements from small to large , Every element we discard , It is necessary to select its next position in the original array , The original array is in ascending order , Therefore, the end point cannot be reduced .
    • that , We can only narrow the range by increasing the starting point , That is, discard the smallest element each time , Replace it with the next element of the original array . Then calculate the length between the current selection , If it is less than the previous interval length, it can be updated .
• The end condition ： When the current smallest element is the last element of its original integer array , It's the end . Because it is impossible to change the starting point for subsequent operations , It will only make the end bigger , That is, the interval becomes longer .

Da Si Lu

• The first number of each array is added to the ordered table , Take the maximum and minimum values , You can find an interval . This interval must cover every array
• Then delete the minimum , Add the next value of this minimum value from the number to the ordered table , Take out the maximum and minimum values again , It forms a new interval , Is it better than the previous interval
• When an array is exhausted , Don't go on , Found the narrowest range

Instance of a

Ordered list

java The ordered table in can be used treeSet, It can find the maximum and minimum values of all arrays in an ordered table

• C++ The ordered table of can be used ：
  • set：key No repetition
  • multiset：key Can be repeated , however erase(key), All its repetition key Will be deleted
  • multimap：
  • priority_queue： It can ensure order and repetition , But the only one priority_queue Only the maximum or minimum value can be checked , You can't check at the same time

What do I do ？

• Use two variables to maintain

class Solution {
    
    //  The smallest pile 
    struct NumGroup{
    
        int num; // The number 
        int grp; // Group number 
        int idx;
        NumGroup(int num, int grp, int idx){
    
            this->num = num;
            this->grp = grp;
            this->idx = idx;
        }

        //  Method 2 defines pq  Overload required  operator>
        bool operator> (const NumGroup &other) const {
    
            return this->num > other.num;
        }
    };

public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
    
        // Because you have to find the smallest element every time , Therefore, it is appropriate to maintain a minimum heap 
        std::priority_queue<NumGroup, std::vector<NumGroup>, std::greater<NumGroup>> minHeap;


        //  The boundary range of the minimum interval 
        int left = 0, right = INT16_MAX;

        //  The minimum and maximum values in the number selected in the current list 
        int  winMin = INT16_MAX, winMax = INT16_MIN;
        for (int i = 0; i < nums.size(); ++i) {
    
            winMax = std::max(winMax, nums[i][0]);
            minHeap.emplace(NumGroup(nums[i][0], i, 0));
        }



        while (true){
    
            //  What pops up is the current minimum 
            int grp = minHeap.top().grp;
            int idx = minHeap.top().idx;
            int num = minHeap.top().num;
            minHeap.pop();


            winMin = num;
            winMax = winMax;



            // The length becomes smaller 
            if(winMax - winMin < right - left){
    
                right = winMax;
                left = winMin;
            }

            //  Judgment of ending in advance 
            if(idx == nums[grp].size() - 1){
    
                break;
            }

            idx++;
            num =  nums[grp][idx];
            minHeap.emplace(NumGroup(num, grp, idx));
            winMax = std::max(winMax, num);
        }
        return {
    left, right};
    }
};