当前位置: 代码迷 >> 综合 >> [leetcode] #239 Sliding Window Maximum (Hard)
  详细解决方案

[leetcode] #239 Sliding Window Maximum (Hard)

热度:14   发布时间:2024-01-05 01:07:05.0

[leetcode] #239 Sliding Window Maximum (Hard)

原题链接

题意:

给定一个数组数字,有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。你只能在窗口看到k个数字。每次滑动窗口向右移动一个位置。

记录每一次窗口内的最大值,返回记录的值。

思路:

解法一:

一开始用的c++迭代器来模拟窗口,每移动一次就遍历一次找出最大值填入返回数组中。

效率非常低 Runtime: 108 ms, faster than 7.98% of C++

class Solution
{
public:vector<int> maxSlidingWindow(vector<int> &nums, int k){int len = nums.size();vector<int> vec;if (len == 0)return vec;vector<int>::iterator iter = nums.begin();for (int i = 0; i + k <= len; i++){vec.push_back(*max_element(iter + i, iter + i + k));}return vec;}
};

解法二:

在Discuss中看到大家普遍用的一直优解思路:

用一个双端队列deque保存每一个窗口里的最大值的索引,同时该队列保存的索引为有序的。

Runtime: 60 ms, faster than 45.44% of C++

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.empty() && dq.front() == i - k)dq.pop_front();while (!dq.empty() && nums[dq.back()] < nums[i])dq.pop_back();dq.push_back(i);if (i >= k - 1)ans.push_back(nums[dq.front()]);}return ans;}
};

 

posted @ 2018-11-06 18:48 Ruoh3kou 阅读( ...) 评论( ...) 编辑 收藏
  相关解决方案