[LeetCode]239.Sliding Window Maximum

2024-02-19 00:32

本文主要是介绍[LeetCode]239.Sliding Window Maximum,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

这里写图片描述

Therefore, return the max sliding window as [3,3,5,5,6,7].Note: 
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.Follow up:
Could you solve it in linear time?

思路

如果采用蛮力法,这个问题似乎不难解决:可以扫描每一个滑动窗口的所有数字并找出其中的最大值。如果滑动窗口的大小为k,需要O(k)时间才能找出滑动窗口里的最大值。对于长度为n的输入数组,这个算法总的时间复杂度是O(nk)。
  实际上一个滑动窗口可以看成是一个队列。当窗口滑动时,处于窗口的第一个数字被删除,同时在窗口的末尾添加一个新的数字。这符合队列的先进先出特性。如果能从队列中找出它的最大数,这个问题也就解决了。
  我们实现了一个可以用O(1)时间得到最小值的栈。同样,也可以用O(1)时间得到栈的最大值。同时我们讨论了如何用两个栈实现一个队列。综合这两个问题的解决方法,我们发现如果把队列用两个栈实现,由于可以用O(1)时间得到栈中的最大值,那么也就可以用O(1)时间得到队列的最大值,因此总的时间复杂度也就降到了O(n)。 我们可以用这个方法来解决问题。不过这样就相当于在一轮面试的时间内要做两个面试题,时间未必够用。再来看看有没有其它的方法。
  下面换一种思路。我们并不把滑动窗口的每个数值都存入队列中,而只把有可能成为滑动窗口最大值的数值存入到一个两端开口的队列。接着以输入数字{2,3,4,2,6,2,5,1}为例一步分析。
  数组的第一个数字是2,把它存入队列中。第二个数字是3.由于它比前一个数字2大,因此2不可能成为滑动窗口中的最大值。2先从队列里删除,再把3存入到队列中。此时队列中只有一个数字3.针对第三个数字4的步骤类似,最终在队列中只剩下一个数字4.此时滑动窗口中已经有3个数字,而它的最大值4位于队列的头部。
  接下来处理第四个数字2。2比队列中的数字4小。当4滑出窗口之后2还是有可能成为滑动窗口的最大值,因此把2存入队列的尾部。现在队列中有两个数字4和2,其中最大值4仍然位于队列的头部。
  下一个数字是6.由于它比队列中已有的数字4和2都大,因此这时4和2已经不可能成为滑动窗口中的最大值。先把4和2从队列中删除,再把数字6存入队列。这个时候最大值6仍然位于队列的头部。
  第六个数字是2.由于它比队列中已有的数字6小,所以2也存入队列的尾部。此时队列中有两个数字,其中最大值6位于队列的头部。
  接下来的数字是5.在队列中已有的两个数字6和2里,2小于5,因此2不可能是一个滑动窗口的最大值,可以把它从队列的尾部删除。删除数字2之后,再把数字5存入队列。此时队列里剩下两个数字6和5,其中位于队列头部的是最大值6.
  数组最后一个数字是1,把1存入队列的尾部。注意到位于队列头部的数字6是数组的第5个数字,此时的滑动窗口已经不包括这个数字了,因此应该把数字6从队列删除。那么怎么知道滑动窗口是否包括一个数字?应该在队列里存入数字在数组里的下标,而不是数值当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时,这个数字已经从滑动窗口中滑出,可以从队列中删除了。

代码

/*---------------------------------------
*   日期:2015-07-19
*   作者:SJF0115
*   题目: 239.Sliding Window Maximum
*   网址:https://leetcode.com/problems/sliding-window-maximum/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <deque>
using namespace std;class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;int size = nums.size();if(size <= 0 || k <= 0){return result;}//if// 双向队列deque<int> deque;for(int i = 0;i < k-1;++i){// 删除小于等于当前元素的值 例如 4 2 1 5while(!deque.empty() && nums[i] >= nums[deque.back()]){deque.pop_back();}//whiledeque.push_back(i);}//for// 不足k个if(size < k){result.push_back(nums[deque.front()]);}//iffor(int i = k-1;i < size;++i){// 删除小于等于当前元素的值while(!deque.empty() && nums[i] >= nums[deque.back()]){deque.pop_back();}//while// 不在滑动窗口之内while(!deque.empty() && i - deque.front() >= k){deque.pop_front();}//whiledeque.push_back(i);result.push_back(nums[deque.front()]);}//forreturn result;}
};int main(){Solution s;int k = 3;vector<int> vec = {4,1,3};//,-1,-2,-3,5,3,6,7vector<int> result = s.maxSlidingWindow(vec,k);for(int i = 0;i < result.size();++i){cout<<result[i]<<" ";}//forcout<<endl;return 0;
}

这篇关于[LeetCode]239.Sliding Window Maximum的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/722947

相关文章

Window Server创建2台服务器的故障转移群集的图文教程

《WindowServer创建2台服务器的故障转移群集的图文教程》本文主要介绍了在WindowsServer系统上创建一个包含两台成员服务器的故障转移群集,文中通过图文示例介绍的非常详细,对大家的... 目录一、 准备条件二、在ServerB安装故障转移群集三、在ServerC安装故障转移群集,操作与Ser

Window Server2016加入AD域的方法步骤

《WindowServer2016加入AD域的方法步骤》:本文主要介绍WindowServer2016加入AD域的方法步骤,包括配置DNS、检测ping通、更改计算机域、输入账号密码、重启服务... 目录一、 准备条件二、配置ServerB加入ServerA的AD域(test.ly)三、查看加入AD域后的变

Window Server2016 AD域的创建的方法步骤

《WindowServer2016AD域的创建的方法步骤》本文主要介绍了WindowServer2016AD域的创建的方法步骤,文中通过图文介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、准备条件二、在ServerA服务器中常见AD域管理器:三、创建AD域,域地址为“test.ly”

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param