21xrx.com
2024-09-20 06:04:12 Friday
登录
文章检索 我的文章 写文章
C++ 单调队列详解
2023-06-28 18:55:57 深夜i     --     --
C++ 单调队列 详解

单调队列是一种非常重要的数据结构,在很多算法中都会用到。本文将详细介绍 C++ 中的单调队列,并讲述它的原理、应用以及使用方法。

什么是单调队列?

单调队列(monotonic queue)是一种能像普通队列一样支持队列头和队列尾的插入、删除和查询最值的数据结构。但与普通队列不同的是,单调队列中的元素是单调递增或单调递减的。

单调队列的核心思想是:维护一个单调递增或单调递减的队列,并通过队列头或队列尾来获取当前最值。当新元素加入队列时,可以选择删除队尾,直到队列中的元素满足单调性。这样每次查询最值时,只需要访问队头或队尾即可。

单调队列的应用

单调队列虽然看似简单,但实际上在算法竞赛中有着广泛的应用。它可以用来解决一系列问题,如图像处理、字符串处理、最大子段和等。

下面介绍几个比较常见的问题:

1.滑动窗口问题

在一个长度为 n 的数组中,求所有长度为 k 的连续子数组的最值。这个问题可以通过滑动窗口算法很好地解决。我们用单调队列来维护窗口内的值,并求出相应的最值。

2.字符串问题

在字符串中求一个子串的最值通常也可以使用单调队列来处理。我们可以将字符串中的每个字符看做一个元素,从而将问题转化为对于一个长度为 n 的数组,找到最长的一段区间,使得区间内的数值单调递增或单调递减。

3.最大子段和问题

最大子段和问题是指在一个长度为 n 的数组中,找到最大子段和。这个问题可以通过动态规划算法和贪心算法来解决。而在贪心算法中,我们可以用单调队列来实现。我们用一个变量 sum 来记录当前最大子段和,用一个变量 ans 来记录最终的结果。

如何使用单调队列?

在 C++ 中,我们可以使用双端队列 std::deque 来实现单调队列。下面是单调队列的基本使用方法:

// 单调递增队列

std::deque incQue;

for (int i = 0; i < n; i++) {

  while (!incQue.empty() && a[i] >= a[incQue.back()]) {

    incQue.pop_back();

  }

  incQue.push_back(i);

  // 删除队头

  if (i - incQue.front() + 1 > k) {

    incQue.pop_front();

  }

  // 输出当前窗口的最大值

  if (i >= k - 1) {

    std::cout << a[incQue.front()] << " ";

  }

}

// 单调递减队列

std::deque decQue;

for (int i = 0; i < n; i++) {

  while (!decQue.empty() && a[i] <= a[decQue.back()]) {

    decQue.pop_back();

  }

  decQue.push_back(i);

  // 删除队头

  if (i - decQue.front() + 1 > k) {

    decQue.pop_front();

  }

  // 输出当前窗口的最小值

  if (i >= k - 1) {

    std::cout << a[decQue.front()] << " ";

  }

}

在上面的代码中,我们分别用双端队列 std::deque 来实现单调递增队列和单调递减队列。代码中的核心部分是对队列的处理以及对当前窗口的最值的计算。

总结

单调队列是一种重要的数据结构,在算法竞赛中有着广泛的应用。它的核心思想是通过维护一个单调递增或单调递减的队列来获取当前最值。要使用单调队列,需要熟悉双端队列的相关操作以及队列头和队列尾的取值方法。在实际开发中,我们可以使用 C++ 的标准模板库中的 std::deque 来实现单调队列。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复