Lintcode362 Sliding Window Maximum solution 题解
发布在Lintcode题解2018年2月26日view:325YiksiAssowIgoriAssowReactthree.jslistManager.jsLinuxvueUI 开发react-native工具WordPressloadreduxf-scriptDenver369CloudBettipostMessagesseCheyanne网页设计bootstrap-tablenpm小程序商店权限控制RESTful
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

给出一个可能包含重复的整数数组,和一个大小为k的滑动窗口, 从左到右在数组中滑动这个窗口,找到数组中每个窗口内的最大值。

【题目链接】

www.lintcode.com/en/problem/sliding-window-maximum/

【题目解析】

遍历数组nums,使用双端队列deque维护滑动窗口内有可能成为最大值元素的数组下标。由于数组中的每一个元素至多只会入队、出队一次,因此均摊时间复杂度为O(n)。记当前下标为i,则滑动窗口的有效下标范围为[i - (k - 1), i]。若deque中的元素下标< i - (k - 1),则将其从队头弹出,deque中的元素按照下标递增顺序从队尾入队。这样就确保deque中的数组下标范围为[i - (k - 1), i],满足滑动窗口的要求。

当下标i从队尾入队时,顺次弹出队列尾部不大于nums[i]的数组下标(这些被弹出的元素由于新元素的加入而变得没有意义)。deque的队头元素即为当前滑动窗口的最大值

【参考答案】

www.jiuzhang.com/solutions/sliding-window-maximum/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

我的收藏