题解 | JZ59 滑动窗口的最大值
滑动窗口这道题是一道经典的题，需要用到双端队列，能在两头进行更新。
这里C++代码中选用了vector作为双端队列的实现。
我们需要记录两个数组，一个是位置的队列，另一个是值的队列。我们需要把这两个信息都记录住才能完成在队列里维护区间最大值的功能。
我们在值的队列中，完成的是维护单调队列的操作。
我们保证val[0]一定是这个区间里的最大值。这样我们只需要在满足条件i>=size-1的时候，直接取出val[0]的值添加到答案队列中即可。
而对于维护val队列而言，我们是需要知道以下两件事就可以了：
1.在值队列里面，要添加进入的值是否比最后的值要小，如果比要添加进入的值要小，需要清除掉
2.在位置队列里面，是否有值不在窗口区了，如果不在，需要清除掉
我们只要完成上面两个操作就是维护了一个单调队列。
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
vector<int> ans;
vector<int> val, pos;
for (int i = 0; i < num.size(); ++i) {
while (pos.size()!=0 && pos[0] <= i-(int)size) {
pos.erase(pos.begin()); val.erase(val.begin());
}
while (pos.size() != 0 && val.back() < num[i]) {
val.erase(val.end()-1); pos.erase(pos.end()-1);
}
pos.push_back(i);
val.push_back(num[i]);
if (i >= size - 1) {
ans.push_back(val[0]);
}
}
return ans;
}
};
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num int整型一维数组
# @param size int整型
# @return int整型一维数组
#
class Solution:
def maxInWindows(self , num: List[int], size: int) -> List[int]:
# write code here
pos = []
val = []
ans = []
if size == 0:
return ans
for i in range(len(num)):
while len(pos)!=0 and pos[0]<= i-size:
pos.pop(0), val.pop(0)
while len(val)!=0 and val[-1] < num[i]:
pos.pop(), val.pop()
pos.append(i)
val.append(num[i])
if i>=size-1:
ans.append(val[0])
return ans
投递美团等公司10个岗位