给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例 1输入nums [1,3,-1,-3,5,3,6,7], k 3输出[3,3,5,5,6,7]解释滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7示例 2输入nums [1], k 1输出[1]提示1 nums.length 105-104 nums[i] 1041 k nums.length我先是这样做的每次移动窗口都判断是否需要重新计算窗口最大值动态刷新窗口最大值class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint res; // 保存结果 if (k 1) { res.insert(res.end(), nums.begin(), nums.end()); return res; } vectorint window; int max nums[0]; int right 0; // 滑动窗口最右边的数在原数组中的索引 window.push_back(nums[0]); for (;right nums.size();) { for (;window.size() k;) { // 初始时窗口数据不够需要持续添加数据 right; window.push_back(nums[right]); if (nums[right] max) { max nums[right]; } } // 窗口数据够了先把最大值加入结果中 res.push_back(max); // 然后窗口向后移动 right; if (right nums.size()) { if (window[0] max) { // 移除窗口第一个数不影响结果 window.erase(window.begin() 0); window.push_back(nums[right]); if (nums[right] max) { max nums[right]; } } else { window.erase(window.begin() 0); // 重新计算最大值 window.push_back(nums[right]); max window[0]; for (int i 1; i window.size(); i) { if (window[i] max) { max window[i]; } } } } } return res; } };运行没问题提交时提示超时重做用队列void testLeeCode239(void) { // 滑动窗口最大值. class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { // 方案1 数据量大时会超时 /* vectorint res; // 保存结果 if (k 1) { res.insert(res.end(), nums.begin(), nums.end()); return res; } vectorint window; int max nums[0]; int right 0; // 滑动窗口最右边的数在原数组中的索引 window.push_back(nums[0]); for (;right nums.size();) { for (;window.size() k;) { // 初始时窗口数据不够需要持续添加数据 right; window.push_back(nums[right]); if (nums[right] max) { max nums[right]; } } // 窗口数据够了先把最大值加入结果中 res.push_back(max); // 然后窗口向后移动 right; if (right nums.size()) { if (window[0] max) { // 移除窗口第一个数不影响结果 window.erase(window.begin() 0); window.push_back(nums[right]); if (nums[right] max) { max nums[right]; } } else { window.erase(window.begin() 0); // 重新计算最大值 window.push_back(nums[right]); max window[0]; for (int i 1; i window.size(); i) { if (window[i] max) { max window[i]; } } } } } return res; */ // 方案2 使用双端队列队列保存数组下标下标对应的值单调递减 vectorint res; dequeint dq; for(int i 0; i nums.size(); i) { // 把队列中小于或等于当前元素的全部删除这样队列索引对应的值保持单调递减。队列第一个索引对应的数最大 // 因为只关心窗口中最大的小的就算被提前移除了也没关系 for (;!dq.empty() nums[i] nums[dq.back()];) { dq.pop_back(); } // 加入最新的索引 dq.push_back(i); // 判断队列首元素对应的数是否过期了移除过期的 // 如果最大的过期移除最大的剩余的最大的没过期其他就算过期了留在队列中也不影响结果 for (;!dq.empty() dq.front() i - k;) { dq.pop_front(); } // 窗口满了就可以记录结果。 if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; } }; }提交ok。