当前位置：首页 > news >正文

旅游公司网站设计/南京网络推广平台

news 2025/6/30 17:23:23

旅游公司网站设计,南京网络推广平台,wordpress拉宽,郑州最好的男科医院有哪些13. 剑指 Offer 59-I. 滑动窗口的最大值要求给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。解题 C版本 #include <iostream> using namespace std; #include <vector> #include <deque>void printVector(vector&l…

13. 剑指 Offer 59-I. 滑动窗口的最大值

要求

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

解题

C++版本

#include <iostream>
using namespace std;
#include <vector>
#include <deque>void printVector(vector<int>& v)
{for (vector<int>::iterator it = v.begin(); it != v.end(); it++){cout << *it << " ";}cout << endl;
}class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> dq;vector<int> ans;for (int i = 0; i < nums.size(); i++) {if (dq.size() && dq.front() <= i - k)  // 删除 deque 中队头dq.pop_front();while (dq.size() && nums[dq.back()] <= nums[i])  // 移除小于当前要加入元素的值的索引dq.pop_back();dq.push_back(i);  // 加入当前索引if (i >= k -1)ans.push_back(nums[dq.front()]); // 记录窗口最大值}return ans;}
};void test01()
{Solution solution;vector<int> nums;nums.push_back(1);nums.push_back(3);nums.push_back(-1);nums.push_back(-3);nums.push_back(5);nums.push_back(3);nums.push_back(6);nums.push_back(7);int k = 3;vector<int> ans;ans = solution.maxSlidingWindow(nums, k);printVector(ans);
}int main()
{test01();system("pause");return 0;
}

在这里插入图片描述

Python版本

import collectionsclass Solution:def maxSlidingWindow(self, nums, k):deque = collections.deque()res = []for i in range(len(nums)):if deque and deque[0] <= i - k:   # 删除 deque 中队头deque.popleft()while deque and nums[deque[-1]] < nums[i]:  # 移除小于当前要加入元素的值的索引deque.pop()deque.append(i)             #  加入当前索引if i >= k-1:res.append(nums[deque[0]])              # 记录窗口最大值return resdef test01():solution = Solution()nums = [1,3,-1,-3,5,3,6,7]k = 3res = solution.maxSlidingWindow(nums,k)print(res)if __name__=="__main__":test01()

在这里插入图片描述

Java版本

package com.hailei_01;import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;public class maxSlidingWindow {public static void main(String[] args) {int[] nums = {1,3,-1,-3,5,3,6,7};int k = 3;System.out.println(maxSlidingWindow(nums,k));}public static ArrayList<Integer> maxSlidingWindow(int[] nums, int k){Deque<Integer> deque = new LinkedList<>();ArrayList<Integer> res = new ArrayList<>();for (int i=0; i<nums.length;i++) {if(!deque.isEmpty() && deque.peekFirst() <=  i-k)deque.removeFirst();while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i])deque.removeLast();deque.addLast(i);if(i>=k-1)res.add(nums[deque.peekFirst()]);}return res;}
}