Re: [閒聊] 每日leetcode
題目:
給你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
噓
10/13 15:39,
1年前
, 1F
10/13 15:39, 1F
噓
10/13 15:43,
1年前
, 2F
10/13 15:43, 2F
→
10/13 15:45,
1年前
, 3F
10/13 15:45, 3F
討論串 (同標題文章)
完整討論串 (本文為第 981 之 1554 篇)：