双指针+贪心思想 – PreLunaの太虚幻境

题目考点

这道题主要考的是：

双指针
贪心思想
列表两端取值
审题后把“文字规则”翻译成“序列单调性”

这题表面上像“堆方块”，本质上其实是在问：

能不能从数组两端依次取数，取出的序列始终保持“不变大”。

也就是：后拿出来放上去的方块，边长不能比下面那个更大。

审题

输入是什么

有 T 组测试数据。

每组数据里：

第一行是方块数量 n
第二行是 n 个整数，表示一排方块的边长

输出是什么

对于每组数据：

如果能按题目要求堆起来，输出 Yes
否则输出 No

题目真正要求我们判断什么

每次只能拿：

最左边的方块
或最右边的方块

而且新堆出来的竖直柱子要满足：

上面的方块不能比下面的大

换句话说，如果我们把“拿方块的顺序”记下来，这个顺序必须是一个**从大到小（允许相等）**的序列。

容易忽略的点

这题最容易卡住的地方有两个：

第一，题目不是让你排序

你不能随便重排，只能从两端拿。

第二，不是去模拟“整个柱子长什么样”

你只需要保证：

当前拿出来的这个方块，不能比前一个已经放好的方块更大。

所以我们只需要记住“上一个放上去的方块大小”。

思路提示

先不要急着看代码，先抓住这题最核心的一句话：

每一步都应该优先拿两端中更大的那个。

为什么？

因为你要让整个取出的序列保持“不变大”。

假设两端分别是 4 和 7：

如果你先拿 4
那么 7 以后就只能放在 4 上面
但 7 > 4，肯定不行

所以更安全的做法是：

先拿大的
小的留到后面

这就是这道题的贪心核心。

你可以先自己记住这个判断模板：

看左端和右端
取较大的那个
判断它是否还能放在当前堆顶上
如果能，继续
如果不能，直接 No

完整设计思路

我们把“已经堆好的最上面那个方块”记成 top。

一开始还没堆，所以 top 可以看成无穷大。
也就是第一个方块无论多大都能放。

然后不断做下面这件事：

第一步：看两端哪个更大

设：

左端是 blocks[left]
右端是 blocks[right]

因为我们最后想形成一个不递增序列，所以优先选较大的那个：

如果左边 >= 右边，就选左边
否则选右边

第二步：判断能不能放

如果选出来的这个值 candidate 满足：

candidate <= top

说明它可以放到当前堆顶上面。

那么：

更新 top = candidate
对应那一侧指针向中间移动

第三步：一旦出现 candidate > top

说明你现在无论怎么选，已经破坏规则了，直接输出 No。

第四步：如果所有方块都处理完了

说明整个过程一直合法，输出 Yes。

为什么这个贪心是对的

这里一定要把道理想透。

我们每一步都在两端里选一个。
假设当前两端是 a 和 b，并且 a < b。

如果你现在选了较小的 a，那么以后 b 还在那里。
可因为 b > a，它以后要放到 a 上面，就不合法了。

所以：

小的可以放在大的上面
大的不能放在小的上面

因此两端都可选时，优先选更大的那个，才是更稳妥的。

这就是这题的贪心依据。

代码实现

下面给你一个适合初学者理解的写法，用双指针，不用真的从列表头部删除元素，因为那样效率低。

t = int(input())

for _ in range(t):
    n = int(input())
    blocks = list(map(int, input().split()))

    left = 0
    right = n - 1
    top = float('inf')   # 当前堆顶，开始时设为无穷大
    possible = True

    while left <= right:
        if blocks[left] >= blocks[right]:
            candidate = blocks[left]
            left += 1
        else:
            candidate = blocks[right]
            right -= 1

        if candidate <= top:
            top = candidate
        else:
            possible = False
            break

    if possible:
        print("Yes")
    else:
        print("No")

运行演示

样例 1

输入：

blocks = [4, 3, 2, 1, 3, 4]

初始：

left 指向 4
right 指向 4
top = 无穷大

第一次

两端是 4 和 4，任选较大，取左边 4

4 <= inf，可以放
top = 4

第二次

两端是 3 和 4，取 4

4 <= 4，可以放
top = 4

第三次

两端是 3 和 3，取 3

3 <= 4，可以放
top = 3

第四次

两端是 2 和 3，取 3

3 <= 3，可以放
top = 3

第五次

两端是 2 和 1，取 2

2 <= 3，可以放
top = 2

第六次

只剩 1

1 <= 2，可以放

全部成功，所以输出：

Yes

样例 2

输入：

blocks = [1, 3, 2]

初始：

左端 1
右端 2
top = inf

第一次

取较大的一端 2

2 <= inf，可以放
top = 2

第二次

现在两端是 1 和 3，取较大的一端 3

但：

3 > 2

说明 3 不能放到 2 上面，失败。

所以输出：

No

方法总结

这类题以后你可以这样识别：

一看到这些特征，就要想到“双指针 + 贪心”

题目如果同时出现下面几个关键词：

只能从两端取
每次取一个
要满足某种大小顺序
问能不能做到

那么大概率就是这类题。

这类题的通用思考套路

先把题目翻译成“序列规则”：

这里的规则就是：取出的顺序必须不递增

然后再想：

每次只能从两端选
为了不让后面更难放，应该优先拿较大的那个

最后用双指针模拟整个过程。

这题最关键的不是代码，而是这句转换

“堆起来合法” = “取出来的序列不能变大”。

一旦你把这句话想明白，代码其实很直。

易错点提醒

1. 想去排序

不能排序。
因为题目限制了只能从两端拿。

2. 用 `pop(0)`

很多初学者会写：

blocks.pop(0)

这个在 Python 里效率很低，因为前面的元素删掉后，后面都要整体前移。

这题数据很大，最好用双指针：

left
right

3. 不是选较小的那个

有些同学会想：“上面要小，那我每次拿小的不就好了？”

这是错的。

因为小的放上去以后，大的可能就再也放不上去了。
所以应该优先拿两端中较大的那个。

本节小结

这题本质不是“堆方块模拟”，而是一个很经典的贪心判断题。

核心只有三步：

维护当前堆顶 top
每次从两端选较大的那个
判断它是否 <= top

能一直放下去就是 Yes，中途有一步放不下就是 No。

练习

你先自己试试这道同类型小练习，不要急着看答案。

练习题

判断下面这组方块能否成功堆起来：

blocks = [5, 4, 3, 2, 1, 6]

输出应该是 Yes 还是 No？

提示

按这题的方法来：

两端比较
每次取较大的那个
记录当前堆顶
看会不会出现“新拿出来的方块比堆顶还大”

你先自己手动模拟一遍。
你要是愿意，我下一条可以继续带你把这题里的这句核心逻辑单独讲透：

if blocks[left] >= blocks[right]:

也可以继续补一节：为什么这题看起来像栈题，但其实更像双指针贪心题。