【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值

简介: 【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值

题目

给你一个整数数组 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 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

示例 2:

输入:nums = [1], k = 1

输出:[1]

参数范围

1 <= nums.length <= 105

-104 <= nums[i] <= 104

1 <= k <= nums.length

单调栈

时间复杂度😮(n)。

queMax中记录(i-k,i],如果i1 < i2,且nums[i1] <=nums[i2],那么i1无论如何都无法成为最大值。故可以淘汰i1,淘汰i1后,成降序排列。队首元素最大。

对queMax有三种操作。

操作一 队尾淘汰i1
操作二 队尾插入i2
操作三 队首删除i-k,由于操作二,queMax不会为空,所以无需判断是否为空。如果i-k已经被操作一淘汰,则不能删除。

代码

核心代码

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int i = 0;
    std::deque<int> queMax;
    vector<int> vRet;
    for ( i = 0; i < k; i++)
    {
      while (queMax.size() && (nums[queMax.back()] <= nums[i]))
      {
        queMax.pop_back();
      }
      queMax.emplace_back(i);     
    }
    vRet.emplace_back(nums[queMax.front()]);
    for (; i < nums.size(); i++)
    {
      if (i - k == queMax.front())
      {
        queMax.pop_front();
      }
      while (queMax.size() && (nums[queMax.back()] <= nums[i]))
      {
        queMax.pop_back();
      }
      queMax.emplace_back(i);
      vRet.emplace_back(nums[queMax.front()]);
    }
    return vRet;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<int> nums;
  int k;
  {
    Solution sln;
    nums = { 1, 3, -1, -3, 5, 3, 6, 7 }, k = 3;
    auto res = sln.maxSlidingWindow(nums, k);
    Assert(vector<int>{ 3,3,5,5,6,7 }, res);
  }
  {
    Solution sln;
    nums = { 1 }, k = 1;
    auto res = sln.maxSlidingWindow(nums, k);
    Assert(vector<int>{ 1 }, res);
  }
//CConsole::Out(res);
}

2023年3月二叉树

用多键二叉树(红黑树)mulset记录滑动窗口中的数,由于二叉树默认是升序排列,所以最后一个元素,就是最大值。由于二叉树的插入、删除的时间复杂度是O(logn),故总时间复杂度是O(nlogn)

class Solution {
 public:
   vector<int> maxSlidingWindow(vector<int>& nums, int k) {
     int i = 0;
     std::multiset<int> setNums;
     for (; i + 1 < k; i++)
     {
       setNums.insert(nums[i]);
     }
     vector<int> vRet;
     for (; i < nums.size(); i++)
     {
       setNums.insert(nums[i]);
       vRet.push_back(*setNums.rbegin());
       auto it = setNums.find(nums[i + 1 - k]);
       setNums.erase(it);
     }
     return vRet;
   }
 };

2023年3月第二版

class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
vector> vValueIndex;
vector vRet;
int iPos = 0;
for (int i = 0; i < nums.size(); i++)
{
while ( ( vValueIndex.size() > iPos ) && (nums[i] >= vValueIndex.back().first))
{
vValueIndex.pop_back();
}
vValueIndex.emplace_back(nums[i], i);
if (i + 1 >= k)
{
vRet.push_back(vValueIndex[iPos].first);
}
if (i + 1 - k == vValueIndex[iPos].second)
{
iPos++;
}
}
return vRet;
}
};

2023年8月版

class Solution{
public:
vector maxSlidingWindow(vector&nums, int k) {
m_c = nums.size();
//每k个元素用一组,vLeft各元素到组首的最大值,vRight各元素到组尾的最大值
vector vLeft(m_c), vRight(m_c);
int iMax = 0;
for (int i = 0; i < m_c; i++)
{
if (0 == i % k)
{
iMax = nums[i];
}
else
{
iMax = max(iMax, nums[i]);
}
vLeft[i] = iMax;
}
iMax = -100 * 1000;
for (int i = m_c-1;i >= 0 ; i-- )
{
if (0 == (i+1) % k)
{
iMax = nums[i];
}
else
{
iMax = max(iMax, nums[i]);
}
vRight[i] = iMax;
}
vector vRet;
for (int i = k-1; i < m_c; i++)
{
vRet.emplace_back( max(vRight[i-k+1], vLeft[i]));
}
return vRet;
}
int m_c;
};


扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17

如无特殊说明,本算法C++ 实现。



相关文章
|
1月前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
32 1
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
57 6
|
1月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
20 2
|
1月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
17 2
|
1月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
16 2
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
1月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
1月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
17 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
18 0
|
1月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
17 0