栈和队列

leetcode04. 滑动窗口最大值

2021-05-19 237 1

简介 leetcode04. 滑动窗口最大值



  1. class Solution {

  2. public:

  3.     vector<intmaxSlidingWindow(vector<int>& nums, int k) {

  4.         vector<int> ans;

  5.         deque<int> dq;   // front 维护为有序

  6.         for(int i = 0; i < nums.size(); i++){

  7.             // 只要当前遍历的元素的值比队尾大,让队尾出队列,

  8.             // 最终队列中的最小元素是大于当前元素的

  9.             while(!dq.empty() && dq.back() < nums[i]) 

  10.                 dq.pop_back();

  11.             // 当前遍历的元素入队列, 此时队列中的元素一定是有序的,队列头部最大

  12.             dq.push_back(nums[i]);

  13.             

  14.             // 窗口满状态,可以得到最大值

  15.             if(i >= k - 1){

  16.                 ans.push_back(dq.front());

  17.                 // 如果窗口即将失效的值(下一次循环要失效)与当前对列头部的值相同,那么将对头的值出队列,

  18.                 // 注意只pop一次,可能两个4,相邻同时是最大值,

  19.                 if(nums[i - k + 1] == dq.front()) 

  20.                     dq.pop_front();

  21.             }

  22.         }

  23.         return ans;

  24.     }

  25. };



  1. class Solution {

  2.     public int[] maxSlidingWindow(int[] nums, int k) {

  3.         int len = nums.length;

  4.         int resultLen = len - k + 1;   // 要返回的数组的长度

  5.         LinkedList<Integer> dq = new LinkedList<Integer>();

  6.         int [] result = new int[resultLen];

  7.         for(int i = 0; i < len; ++i) {

  8.             // 只要当前遍历的元素的值比队尾大,让队尾出队列,

  9.             // 最终队列中的最小元素是大于当前元素的

  10.             while(!dq.isEmpty() && nums[i] > dq.peekLast()) {

  11.                 dq.pollLast();

  12.             }

  13.             // 当前遍历的元素入队列, 此时队列中的元素一定是有序的,队列头部最大

  14.             dq.addLast(nums[i]);

  15.             // 窗口满状态,可以得到最大值

  16.             if(i >= k - 1) {

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

  18.                  // 如果窗口即将失效(下一次循环要失效)的值与当前对列头部的值相同,那么将对头的值出队列,

  19.                 // 注意只pop一次,可能两个4,相邻同时是最大值,

  20.                 if(nums[i - k + 1] == dq.peekFirst())

  21.                     dq.pollFirst();

  22.             }

  23.         }

  24.         return result;

  25.     }

  26. }

{

    [] ([] 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;

    }

}



点赞 1

文章评论

欢迎您:

纸上得来终觉浅,绝知此事要躬行!

112 文章 36783 浏览 3 评论

联系我

  •   QQ:    361352119
  •  Email:  lisimmy@sina.com
  • 微信: