1. 例题

题目描述

一个数列包含 n 个正整数，请按顺序输出数列中每一个数前面第一个（距离自己最近）比自己大的数。如果不存在这样的数请在对应位置输出 0。

输入格式

第 1 行：1 个正整数 n （ 1 <= n <= 300000 )。

第 2 行: n 个正整数 $a_i$ ( 1<= $a_i$ <= ${10}^{10}$）

输出格式

一行， n 个整数，用空格隔开。

样例

10
31 20 48 61 39 25 35 12 48 37 

0 31 0 0 61 39 39 35 61 48

2. 执行过程

在之前的课程，我们学过了链表算法，链表的核心就是“跳，跳，跳”，不是按顺序的逐个去看，跳过了很多无用的垃圾数据。如果当前这个数不够大，就跳到第一个比它的大数哪里，继续循环的比较和跳。

现在，我们学习一种新的算法，它的做法和 “跳，跳，跳” 有类似之处，但是它是通过维护一个队列来让问题更加容易实现，代码会更简单。而且，这个算法可以应用于更复杂的题目。

我们先看看样例中的 10 个数，如果用图表来表示，会是下面这样的一个形态：

这种图叫柱状图，也叫直方图，用柱子来表示数字，数字越大，柱子越高。题目说，要找前方距离自己最近的、又要比自己大的数字，那么换成图像思维，就是要找左方第一根比自己高的柱子。

1. 第 1 个数字 31，前方没有数字了，所以，输出 0

2. 第 2 个数字 20，它前方的第一个数字就比它大，所以，输出前方的数字 31

上面这两个数字都没问题，很简单

3. 第 3 个数字是 48，它前方没有数字比它大，输出 0 。我们先假设这一次我们是暴力方法看完了前面 2 个数字。

处理完了 3 个数字之后，图像是这样的：

我们回顾一下，上面说过，本质上，就是要找左方第一根比自己高的柱子。现在第 1 和第 2 根柱子都比第 3 根柱子矮，这里总觉得有点什么不对，可以做点什么事情。

其实，前面的这 2 根柱子已经是无效数据了。因为假设第 4 个数字是一个比 第 3 个数字小的的数，左方第一根比自己高的柱子就是第 3 根柱子，和 1,2 柱子无关；如果第 4 个数字是一个大于等于第 3 个数字的数，那也跟 1,2 柱子无关，因为它们更加不够高。所以，无论如何，1,2 柱子在这个时候已经是废物了，可以删掉。

删掉 1，2 柱子之后，图像变成下面这样：

4. 第 4 个数字是 61，而因为这时候前面只有 1 根柱子，只需要 1 次比较就结束了，意味着 61 前面是没有比 61 更高的柱子的。同样道理，因为 61 比 41 高，41 已经没有存在的意义了，我们又扔掉了 41 这根柱子。

5. 第 5 个数字是 39 ，很简单，左边的柱子是 61 ，比 39 高，所以它一下子就找到了第一根比自己高的柱子，39 比 61 小，它是有用的，这根柱子要留下来。同样，第 6 个数字 25，用同样的方法快速找到了第一根比自己高的柱子 39。这时候，图像变成下面这样：

6. 第 6 个数字是 35，它前面有 3 根柱子，第一根是 25，比自己矮，第二根是 39 ， 比自己高，所以，39 就是它要找的数。而因为 37 比 25 高，25 没有存在的意义了，它是垃圾数据，把它扔掉。图像就变成了下面这样：

7. 第 7 个数字是 12，它左边的第一根柱子就比自己高了，马上找到了答案，图像变成这样：

8. 第 8 个数字是 48 ，它往前看，一直找到 61 才找到了第 1 根比自己高的数字，它前面那些矮柱子可以扔掉，变成下图：

9. 第 9 个数字是 37，它一下子找到了前面第一根比自己高的柱子：48

3. 算法分析和整理

1. 在基于链表的算法中，无用数据并没有被删除，我们是通过了一个前跳指针指向前方第 1 个比自己大的数。因为数据没有删掉，所以，找数据的时候就是“跳，跳，跳”，跳过了无用的数据。

2. 在现在学的新算法当中，无用数据被清理删除，留下来的数据都是有用（或者说，不能排除它有用）。删完的数据一般没剩多少，在查找的时候可以按顺序来查（数据量大的时候，还可以进一步叠加二分查抄算法）。

所以，两种算法的一些精髓是一样的，但是在细节上走了不同的路线。下面，我们见一下这个新算法的操作步骤。

1. 这个算法叫 单调栈。栈的特点是先入后出，这和队列的特性先入先入相反。但是，作为小朋友我们先不要太关注这些理论性的东西（除非你很聪明，思路非常非常清晰），我们就只管使用就好了。在上面的例子中，我们总是试图扔掉尾巴部分的一些没用的东西，扔掉东西的过程叫出栈，最后把新来的数字加到尾巴那里去教入栈，有没有留意到，这个算法里面并没有从队头去取数据。上面这些图像里，留下来的数据总是呈现出单调性，这一题，就是单调递减栈，删除无用数据之后，剩下来的柱子是从左到右越来越矮的，类似，还有单调递增栈，思想是一样的。（除了单调栈之外，的确还有单调队列，我们会在其它题目中讲述）。

2. 删垃圾数据的过程就是出栈了，可以用 STL 的 stack 模板，自己写个数组来实现也可以。

3. 详细步骤是：

   • 来了新数据之后，先检查栈尾部有没有垃圾数据，如果有就删除（出栈）

   • 删除完之后，如果栈已经空了，就表示没有符合要求的数（查找失败），如果有，就输出栈顶数据

   • 把新来的数据入栈

4. 程序填空

#include<bits/stdc++.h>
using namespace std;
int s[300001],n,top; 
int main()
{
	scanf("%d",&n);

	top= 填空(1) ;
	int t;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t);
		
		//无用数据出栈
		while(top>=1 && 填空(2) )
			top--;
		
		//这个地方很巧妙，如果栈空了，top 为 0 
		printf("%d ",填空(3) ); 
		
		//新来的数入栈顶
		填空(4);
		
	}
	
	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}