設(shè)數(shù)組大小為N纠修，滑動(dòng)窗口大小為K
1. 常規(guī)思路
常規(guī)思路：遍歷數(shù)組祝拯，每次計(jì)算最大值滤愕，或者遍歷K次温算，將題目化為兩個(gè)窗口的方法，時(shí)間復(fù)雜度為O(N*K), 顯然不滿足需求间影。
2. 最大堆
其實(shí)做過(guò)“尋找n個(gè)無(wú)窮數(shù)中尋找最大的K個(gè)數(shù)”這題的話注竿，應(yīng)該比較容易想到，用堆來(lái)處理這種“求連續(xù)輸入的數(shù)據(jù)中的最值”的題目魂贬。思路還是比較像的巩割。
具體思路：
構(gòu)建一個(gè)大小為K的最大堆，每次從堆中取出窗口的最大值付燥，隨著窗口往右滑動(dòng)宣谈，需要將堆中不屬于窗口的堆頂元素刪除。
這里的堆键科，我們直接使用STL中的優(yōu)先隊(duì)列priority_queue（可以理解為另一種形式的堆）
代碼如下闻丑，復(fù)雜度為O(N*logN)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
vector<int> result;
priority_queue<pair<int,int>> Q; //pair.second記錄原始數(shù)據(jù)的序號(hào)漩怎，從而便于識(shí)別最大值是否在當(dāng)前窗口內(nèi)，其實(shí)也可以只存儲(chǔ)編號(hào)
if (nums.size() < k || k < 1)
return result;
for (int i = 0; i < k-1; i++)
Q.push(pair<int,int>(nums[i],i));
for (int i = k-1; i < nums.size(); i++)
{
Q.push(pair<int,int>(nums[i],i));
pair<int,int> p = Q.top();
while(p.second < i-(k-1))
{
Q.pop();
p = Q.top();
}
result.push_back(p.first);
}
return result;
}
};
其實(shí)在仔細(xì)考慮會(huì)想到嗦嗡，并不需要一直維護(hù)一個(gè)大小為K的堆勋锤。
3. 集合
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
vector<int> result;
if (k == 0) return result;
multiset<int> w;
for (int i = 0, n = nums.size(); i < n; i++)
{
if (i >= k)
w.erase(w.find(nums[i-k]));
w.insert(nums[i]);
if (i >= k-1)
result.push_back(*w.rbegin());
}
return result;
}
};
3. 雙端隊(duì)列
使用雙端隊(duì)列，隊(duì)列元素降序排序侥祭，隊(duì)首元素為所求最大值叁执。滑動(dòng)窗口右移卑硫，若出現(xiàn)的元素比隊(duì)首（最大元素）大徒恋，此時(shí)清空隊(duì)列蚕断，并將最大值插入隊(duì)列欢伏。若比當(dāng)前值小，則插入尾部亿乳。每次窗口右移的時(shí)候需要判斷當(dāng)前的最大值是否在有效范圍硝拧，若不在，則需要將其從隊(duì)列中刪除葛假。
給出代碼障陶，時(shí)間復(fù)雜度為O(N)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
vector<int> result;
deque<int> Q;//隊(duì)列記錄的是編號(hào)
if(nums.size() < k || k <= 0)
return result;
for (int i = 0; i < k; i++)
{
while (!Q.empty() && nums[i] > nums[Q.back()])
Q.pop_back();
Q.push_back(i);
}
for (int i = k; i < nums.size(); i++)
{
result.push_back(nums[Q.front()]);
while (!Q.empty() && nums[i] >= nums[Q.back()]) Q.pop_back();
while (!Q.empty() && Q.front() <= i - k) Q.pop_front();
Q.push_back(i);
}
result.push_back(nums[Q.front()]);
return result;
}
};
4. 某位大神的O(n)解法
大致思路就是對(duì)窗口值對(duì)數(shù)組進(jìn)行分段，然后左右分別計(jì)算區(qū)域內(nèi)最大值聊训，最后歸并抱究。感覺(jué)非常smart啊。這個(gè)方法值得好好歸納一下带斑，好像之前某些題也有類似的做法鼓寺。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
int n = nums.size();
vector <int> res;
if(n == 0) return res;
if(k == 1) return nums;
int left[n];
int right[n];
left[0] = nums[0];
right[n - 1] = nums[n - 1];
for(int i = 0;i < n;i++)
{
if(i % k == 0)
left[i] = nums[i];
else
left[i] = std::max(nums[i],left[i - 1]);
}
for(int i = n - 2;i >= 0;i--)
{
if(i % k == 0)
right[i] = nums[i];
else
right[i] = std::max(nums[i],right[i + 1]);
}
for(int i = 0; i <= n - k;i++)
{
res.push_back(std::max(right[i],left[i + k - 1]));
}
return res;
}
};
5. 其他
還有使用棧O(n)解法等，等后續(xù)再慢慢看勋磕。
參考文獻(xiàn)
3 C++ Solutions
C++ Time O(N) Space O(N), Use Max Queue.
Not the best,but the fastest,beat 97%
