---
title: "（未解决）双端队列"
created: 2025-11-28
tags:
  - 算法
---

# （未解决）双端队列

## 题目 [双端队列](https://www.acwing.com/problem/content/description/136/)

![[image-3138d2dd.png]]

## 思路分析

![[image-ac0ddc1f.png]]

![[image-c1a26d42.png]]

![[image-31dd76e0.png]]

![[image-67b12d1e.png]]

![[image-6b571381.png]]

## 代码实现

```cpp
#include <algorithm>

#include <iostream>

using namespace std;

const int N = 2e5 + 10;

typedef pair<int, int> PII;

#define value first

#define before_sort second

PII a[N];

int n;

int main() {

    cin >> n;

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

        cin >> a[i].value;

        a[i].before_sort = i;

    }

    sort(a, a + n);

    int res = 1;  // 最后最少分成的段数

    // last记录一下上一个值(上一段的最后一个值是多少),

    // 初始化为比所有坐标都大即可(>n的数字均可) dir用来记录方向

    // 第一条边一定是下降的, 因此dir初始化为-1(可以理解为是从上面接下来的)

    for (int i = 0, last = n + 1, dir = -1; i < n;) {

        int j = i + 1;

        // 找到一段相等的数值

        // 如果这一段的数字是相等的, 那么这些下标是可以随意变换的

        // 从i-j-1这一段, 都是和a[i].value相同的数字

        while (j < n && a[j].value == a[i].value) {

            j++;

        }

        // 找到这一段中的最大的下标和最小的下标

        // 因为是sort(pair经过sort)过的, 因此minx一定这一段的第一个数的位置

        // maxx一定是这一段的最后一个数的位置

        // 在原序列中的的位置

        // minx=a[i].before_sort, maax = a[j-1].before_sort;

        // 我们处理的时候是一个点一个点进行处理的(如果有相同的, 则处理一段,

        // 因为相同的可以任意插入到一个双端队列)

        int minx = a[i].before_sort, maxx = a[j - 1].before_sort;

        if (dir == -1) {        //如果是下降的, 如何做?

            if (last > maxx) {  //如果上一个位置>当前的最大位置,

                                //那么就可以接到上一个位置的后面

                last =

                    minx;  // 接上了的话, 这一段的最后一个数值(原坐标)应该是minx

            } else {  //如果没有接上, 那么更新方向为上升, last=maxx

                      // 此时不需要res++的原因是 谷是先下降, 后上升的

                      // 上升结束之后, 才需要开启新的谷

                dir = 1, last = maxx;  // 上升的时候last更新为最大值,

            }

        } else {  // 如果是上升的, 如何做?

            if (last <

                minx) {  // 如果last比我当前这一段的最小值还要小, 那么可以接上去

                last = maxx;

            } else {  // 否则开新双端队列+更新last为这一段的最小值,

                      // 更新方向为下降

                res++;

                last = minx;

                dir = -1;

            }

        }

        i = j;

    }

    cout << res << endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[逛画展|逛画展]] 🏠 [[00-刷题理模型]] ➡️ [[AC自动机|AC自动机]]