在日常的算法面试和刷题过程中,滑动窗口问题是非常常见的类型。今天我们来详细解答如何通过单调队列的方法找到滑动窗口中的最小值,并通过具体代码示例和步骤拆解,帮助大家更好地理解这一算法。

问题描述

给定一个数组和一个整数 k,我们需要找到该数组中每个大小为 k 的连续子数组中的最小值。

举例来说,给定数组 a = [2, 1, 3, 4, 5],窗口大小为 k=3,我们需要找到以下滑动窗口中的最小值:

  • [2, 1, 3] 的最小值为 1
  • [1, 3, 4] 的最小值为 1
  • [3, 4, 5] 的最小值为 3

输出结果应该是:1 1 3

思路

我们使用单调队列来解决这一问题。队列中存储的是数组中元素的下标,队列中的元素保持单调递减。这样队头元素总是滑动窗口的最小值。

主要步骤:

  1. 保持队列单调性:当有新的元素进入窗口时,我们需要移除队列中比新元素大的值,因为这些值在窗口中已经不可能成为最小值。
  2. 移除过期元素:当滑动窗口右移时,窗口中最左边的元素可能已经超出了窗口范围,我们需要从队列中移除它。
  3. 输出当前窗口的最小值:当窗口大小达到 k 时,输出队头元素即为当前窗口的最小值。

代码实现

int hh = 0, tt = -1;  // 初始化队列的头和尾指针
for (int i = 1; i <= n; i++) {
    // 判断队头是否在窗口范围内,不在则移除
    if (hh <= tt && q[hh] < i - k + 1) hh++;
    
    // 保持队列单调递减,移除比当前元素大的队尾元素
    while (hh <= tt && a[i] <= a[q[tt]]) tt--;
    
    // 当前元素入队
    q[++tt] = i;
    
    // 窗口达到大小 k 时,输出当前窗口的最小值
    if (i > k - 1) cout << a[q[hh]] << " ";
}
puts("");  // 输出完毕后换行

详细示例分析

我们以 a = [2, 1, 3, 4, 5]k=3 为例,通过每一步的分析,帮助大家更好地理解代码的执行过程。

第 1 步 (i=1):

  • 当前元素:a[1] = 2
  • 判断是否移除队头元素:队列为空,不执行移除操作。
  • 判断是否保持单调性:队列为空,不执行移除操作。
  • a[1] 的下标 1 入队,队列状态:q = [1]
  • 当前窗口还不足 k 个元素,不输出最小值。

第 2 步 (i=2):

  • 当前元素:a[2] = 1
  • 判断是否移除队头元素:队列头元素 q[hh] = 1 还在窗口范围内,不移除。
  • 保持单调性:当前元素 a[2] = 1 小于队尾元素 a[1] = 2,移除队尾元素。
  • a[2] 的下标 2 入队,队列状态:q = [2]
  • 当前窗口还不足 k 个元素,不输出最小值。

第 3 步 (i=3):

  • 当前元素:a[3] = 3
  • 判断是否移除队头元素:队列头元素 q[hh] = 2 还在窗口范围内,不移除。
  • 保持单调性:当前元素 a[3] = 3 大于队尾元素 a[2] = 1,不移除队尾元素。
  • a[3] 的下标 3 入队,队列状态:q = [2, 3]
  • 当前窗口已达到 k 个元素,输出当前窗口的最小值 a[q[hh]] = a[2] = 1
  • 输出:1

第 4 步 (i=4):

  • 当前元素:a[4] = 4
  • 判断是否移除队头元素:队列头元素 q[hh] = 2 超出窗口范围,移除队头元素。
  • 保持单调性:当前元素 a[4] = 4 大于队尾元素 a[3] = 3,不移除队尾元素。
  • a[4] 的下标 4 入队,队列状态:q = [3, 4]
  • 当前窗口已达到 k 个元素,输出当前窗口的最小值 a[q[hh]] = a[3] = 1
  • 输出:1

第 5 步 (i=5):

  • 当前元素:a[5] = 5
  • 判断是否移除队头元素:队列头元素 q[hh] = 3 还在窗口范围内,不移除。
  • 保持单调性:当前元素 a[5] = 5 大于队尾元素 a[4] = 4,不移除队尾元素。
  • a[5] 的下标 5 入队,队列状态:q = [3, 4, 5]
  • 当前窗口已达到 k 个元素,输出当前窗口的最小值 a[q[hh]] = a[3] = 3
  • 输出:3

最终输出:

1 1 3

关键部分解释

  1. 移除队头元素

    if (hh <= tt && q[hh] < i - k + 1) hh++;

    这个条件判断队列头元素是否超出了当前窗口范围,如果队头下标不在窗口内,就将其移除。

  2. 保持单调队列

    while (hh <= tt && a[i] <= a[q[tt]]) tt--;

    我们需要保证队列中的元素保持单调递减。每当有新元素加入队列时,我们移除所有比它大的元素,因为这些较大的元素在当前窗口中不可能再成为最小值。

  3. 输出最小值

    if (i > k - 1) cout << a[q[hh]] << " ";

    当遍历到第 k 个元素及以后时,窗口的大小达到 k,此时输出队列头的元素作为当前窗口的最小值。

总结

通过使用单调队列,我们能够高效地解决滑动窗口最小值问题。时间复杂度为 O(n),因为每个元素最多入队和出队各一次。单调队列是一种非常有用的技巧,特别是在涉及动态范围查询的问题时。

之前买的gv号,可能是因为我一直发一些无意义的短信例如“1”或图片来保号,结果号被封了。
然后我登我自己的google邮箱,发现好像可以领账号了,就是这么神奇,突然可以用了。
我怀疑,现在如果我用指纹浏览器再去注册一个gv号应该也是可以的,但是不是很想搞。
有一个在自己邮箱上就很满足了。现在就是主要有两个虚拟号,一个是gv另外一个就是talkatone。
我发现如果只是来玩的话,其实talkatone的可玩性或许会高一点,因为他的成本比较低,只要一个静态ip就行。

大家好!这篇文章将带你一步步配置 Windows 上的 C++ 开发环境。这是为新手准备的详细教程,无论你之前有没有编程经验,都可以轻松跟随完成。我们将使用 MinGW-W64 作为编译器,Visual Studio Code (VSCode) 作为代码编辑器。让我们从下载工具开始!

第一步:下载 MinGW-W64 GCC 编译器

我们需要一个编译器来将 C++ 代码转换成计算机可以执行的程序。这里我们选择 MinGW-W64 GCC 8.1.0 作为我们的编译工具。

下载链接MinGW-W64 8.1.0

点击链接,下载这个压缩包。

第二步:解压 MinGW-W64

下载完成后,将压缩包解压到你电脑上的一个文件夹里,注意:确保文件夹路径中不要有空格或中文字符。比如可以直接解压到 C:\MinGW 这样的目录。

第三步:配置环境变量

接下来,我们需要让系统知道编译器的位置,这样以后我们就可以在任何地方使用它了。

  1. 在 Windows 搜索栏里输入 环境变量,点击“编辑系统环境变量”。
  2. 点击“环境变量”按钮。
  3. 在“系统变量”中,找到 Path,选中后点击“编辑”。
  4. 点击“新建”,在这里输入你刚才解压 MinGW 的路径,记得要包含 bin 文件夹,比如 C:\MinGW\bin
  5. 保存设置,点击“确定”退出所有窗口。

验证:打开命令提示符(按 Win + R,输入 cmd),然后输入 g++ --version,如果你看到类似 g++ (x86_64-posix-sjlj-rev0, Built by MinGW-W64 project) 8.1.0 的输出,那么说明你已经成功配置好了。

第四步:安装 VSCode 和 C++ 插件

为了编写和运行 C++ 代码,我们需要一个编辑器。这里推荐使用 Visual Studio Code (VSCode),它轻量、强大且支持多种语言。

  1. 前往 VSCode官网 下载并安装 VSCode。
  2. 打开 VSCode,点击左侧的“扩展”图标(或按 Ctrl+Shift+X),搜索 C++
  3. 安装由微软提供的 C++ 插件,这会使 VSCode 具有 C++ 代码智能提示和调试功能。

第五步:编写第一个 C++ 程序

现在,我们来编写并运行我们的第一个 C++ 程序。

  1. 新建一个文件夹,比如 C:\MyCPPProjects,在 VSCode 中选择“打开文件夹”。
  2. 在这个文件夹中,新建一个文件,命名为 test.cpp
  3. test.cpp 中输入以下代码:

#include <iostream>

  

int main() {

    std::cout << "Hello, World!" << std::endl;

    return 0;

}
  1. 保存文件,然后按 F5 运行程序。第一次运行时,VSCode 会提示你选择调试配置,选择 g++ (编译并调试活动文件)
  2. 接下来会要求你选择编译器,选择 g++

第六步:完成配置并运行

现在,VSCode 会帮你编译并运行程序,如果一切顺利,你将在控制台中看到输出:


Hello, World!

恭喜你!你已经成功完成了 C++ 环境的搭建,并运行了你的第一个 C++ 程序。

常见问题解答

  1. 命令行找不到 g++

   - 请确保你在系统环境变量中正确添加了 MinGW 的 bin 目录。

  1. VSCode 无法找到编译器

   - 确保 MinGW 已经正确安装,并且系统环境变量配置无误。如果仍然有问题,尝试重启 VSCode 或重新配置环境。

结语

通过这篇教程,你已经学会了如何下载、安装并配置 MinGW-W64 作为 C++ 编译器,如何使用 VSCode 编写并运行 C++ 程序。希望你能够继续学习 C++,创造出更多有趣的项目。如果有任何问题,欢迎在评论区留言,我会尽力解答。

Happy coding!

一、n的二进制表示中第k位是几
第一步:将n右移k位,即 n >> k,把第k位移到最低位。
第二步:通过与运算获取最低位的值,即 n & 1,判断第k位是0还是1。

二、lowbit(x):返回x的最低位1及其后所有0所组成的数值

例如:
x = 1010(二进制) lowbit(x) = 10
x = 101000(二进制) lowbit(x) = 1000

原理:
lowbit(x) 的计算公式是 x & -x。

解释:

  • 首先,-x 等于 ~x + 1,这是二进制表示中取反加一的结果(即补码)。
  • 当我们将x与-x进行按位与运算时,结果会保留x中最低位的1,并将其他位清零。

举例说明:
x = 1010010101000
~x = 0101101010111
-x = ~x + 1 = 0101101011000(补码)
x & -x = 0000000001000

这表明lowbit(x) = 1000。

应用:
可以用lowbit(x)来计算x(二进制)中有多少个1。