Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

題目:
給你vector<vector<int>>
找一個最短區間
包含到所有vector<int>的元素

思路:
sliding window 跟merge sort的感覺
動右邊的時候
每次都看有沒有包含到全部
更新
然後更新priority queue追蹤新的元素
要動左邊的話
用deque來看就好




休息一下

```cpp
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums)
    {
        int len = nums.size();

        vector<int> cnt(len , 0);
        vector<int> idxlist(len, 1);
        priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,
int>>> paper;

        for(int i = 0 ; i < len ; i ++)paper.push({nums[i][0] , i});


        vector<int> res(2);
        int resv = 99999999;
        deque<pair<int,int>> save;

        int check = 0;
        while(!paper.empty())
        {

            while(check < len && !paper.empty())
            {
                int val = paper.top().first;
                int idx = paper.top().second;
                paper.pop();

                if(idxlist[idx] < nums[idx].size()) {
                    paper.push( { nums[idx][idxlist[idx]] , idx });
                    idxlist[idx] ++;
                }

                if(cnt[idx] == 0)check++;
                cnt[idx] ++;

                save.push_back({val,idx});
            }

            if( (check >= len) && save.back().first -save.front().first < resv){
                resv = save.back().first -save.front().first;
                res[0] = save.front().first;
                res[1] = save.back().first;
            }

            while(check >= len)
            {
                pair<int,int> now = save.front();
                int val = now.first;
                int idx = now.second;
                save.pop_front();

                cnt[idx] --;
                if(cnt[idx] == 0)
                {
                    check--;
                    break;
                }

                if( (check >= len) &&   save.back().first -save.front().first <
resv)
                {
                    resv = save.back().first -save.front().first;
                    res[0] = save.front().first;
                    res[1] = save.back().first;
                }
            }

        }

        return res;

    }
};
```



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.19.26 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728805145.A.B5A.html
噓 mrsonic: 刷爽沒
噓 DJYOSHITAKA: 刷爽沒
→ oin1104: .