栈和队列

leetcode04. 滑动窗口最大值

2021-05-19 357 1

简介 leetcode04. 滑动窗口最大值

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
deque<int> dq; // front 维护为有序
for(int i = 0; i < nums.size(); i++){
// 只要当前遍历的元素的值比队尾大，让队尾出队列，
// 最终队列中的最小元素是大于当前元素的
while(!dq.empty() && dq.back() < nums[i])
dq.pop_back();
// 当前遍历的元素入队列，此时队列中的元素一定是有序的，队列头部最大
dq.push_back(nums[i]);
// 窗口满状态，可以得到最大值
if(i >= k - 1){
ans.push_back(dq.front());
// 如果窗口即将失效的值（下一次循环要失效）与当前对列头部的值相同，那么将对头的值出队列，
// 注意只pop一次，可能两个4，相邻同时是最大值，
if(nums[i - k + 1] == dq.front())
dq.pop_front();
}
}
return ans;
}
};

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
int resultLen = len - k + 1; // 要返回的数组的长度
LinkedList<Integer> dq = new LinkedList<Integer>();
int [] result = new int[resultLen];
for(int i = 0; i < len; ++i) {
// 只要当前遍历的元素的值比队尾大，让队尾出队列，
// 最终队列中的最小元素是大于当前元素的
while(!dq.isEmpty() && nums[i] > dq.peekLast()) {
dq.pollLast();
}
// 当前遍历的元素入队列，此时队列中的元素一定是有序的，队列头部最大
dq.addLast(nums[i]);
// 窗口满状态，可以得到最大值
if(i >= k - 1) {
result[j++] = dq.peekFirst();
// 如果窗口即将失效（下一次循环要失效）的值与当前对列头部的值相同，那么将对头的值出队列，
// 注意只pop一次，可能两个4，相邻同时是最大值，
if(nums[i - k + 1] == dq.peekFirst())
dq.pollFirst();
}
}
return result;
}
}

{

    [] ([] nums, k) {


        len = nums.;

        resultLen = len - k + ;   <> dq = LinkedList<>();

        [] result = [resultLen];


        (i = ; i < len; ++i) {

            (!dq.() && nums[i] > dq.()) {

                dq.();

            }

            dq.(nums[i]);


            (i >= k - ) {

                result[j++] = dq.();


                (nums[i - k + ] == dq.())

                    dq.();

            }

        }

        result;

    }

}