dede怎么做网站,做一个网站,东营网站seo外包,灰色关键词网站建设239. 滑动窗口最大值
解题思路
计算每一个滑动窗口的最大值 关键在于借助单调队列实现窗口对于单调队列 尾部添加元素 头部删除元素添加元素操作#xff1a;从尾部开始循环对比 删除比当前元素小的元素获取最大值元素 直接获取头部元素删除元素操作 直接删除头部元素
class…239. 滑动窗口最大值
解题思路
计算每一个滑动窗口的最大值 关键在于借助单调队列实现窗口对于单调队列 尾部添加元素 头部删除元素添加元素操作从尾部开始循环对比 删除比当前元素小的元素获取最大值元素 直接获取头部元素删除元素操作 直接删除头部元素
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 借助单调队列 计算每一个滑动窗口的最大值MonotonicQueue window new MonotonicQueue();// 单调队列窗口ListInteger res new ArrayList();for(int i 0; i nums.length; i){if(i k - 1){window.push(nums[i]);// 先把前面k- 1 个元素填满}else{// 窗口开始向前面移动// 移入新的元素window.push(nums[i]);// 因为是单调队列 直接计算最大值res.add(window.max());// 移除最后的元素window.pop(nums[i - k 1]);}}// 将List 类型转换为int[] 数组 作为返回值int[] arr new int[res.size()];for(int i 0; i res.size(); i){arr[i] res.get(i);}return arr;}// 单调队列的实现 尾部添加元素 头部删除元素 那么头部元素是最大值// 维护的单调队列 是需要从尾部到头部的元素 全部单调递增class MonotonicQueue{// 使用双链表 模拟队列 支持头部和尾部添加和删除元素private LinkedListInteger maxq new LinkedList();public void push(int n){// 尾部添加一个元素 需要维护单调队列 从尾部到头部 单调递增的性质// 从尾部开始 将前面小于她的元素 全部删除掉 这样维护的就是一个单调队列while(!maxq.isEmpty() maxq.getLast() n){maxq.pollLast();// 删除尾部元素}maxq.addLast(n);// 添加元素 尾部添加元素}// 计算最大元素 直接就是取出 头部元素 因为头部元素最大public int max(){return maxq.getFirst();}// 头部删除元素public void pop(int n){if(n maxq.getFirst()){maxq.pollFirst();}}}
}
