362. Sliding Window Maximum
class Solution {
public:
/**
* @param nums: A list of integers.
* @param k: An integer
* @return: The maximum number inside the window at each moving.
*/
vector<int> maxSlidingWindow(vector<int> &nums, int k) {
// write your code here
// max stack
// 开始想用stack，但发现这里是先进先出。
// 要用queue，但为了要左右两端都可以pop，要用double end queue
//
//stack<int> stk;
//stack<int> maxStk;
std::deque<int> dq;
const int size = nums.size();
vector<int> res;
if(k == 0){
return res;
}
if(size < k){
int maxN = INT_MIN;
for(auto i : nums){
maxN = max(maxN, i);
}
res.push_back(maxN);
return res;
}
for(int i = 0; i < k; i++){
while(!dq.empty() && nums[i] > dq.back()){
dq.pop_back();
}
dq.push_back(nums[i]);
}
//vector<int> res;
res.push_back(dq.front());
for(int i = k; i < size; i++){
if(dq.front() == nums[i - k]){
dq.pop_front();
}
while(!dq.empty() && nums[i] > dq.back()){
dq.pop_back();
}
dq.push_back(nums[i]);
res.push_back(dq.front());
}
return res;
}
};
Comments
Post a Comment