[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 == )

      return vec;

    vector<int>::iterator iter = nums.begin();

    for (int i = ; 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 = ; 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 - )

        ans.push_back(nums[dq.front()]);

    }

    return ans;

  }

};

巴特西

[leetcode] #239 Sliding Window Maximum (Hard)

最新文章

热门文章