Problem5755--学习系列——单调栈 I——构建单调递减栈

5755: 学习系列——单调栈 I——构建单调递减栈

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

【知识点】
单调栈中存放的数据应该是有序的,所以单调栈也分为单调递增栈和单调递减栈
  • 单调递增栈:单调递增栈就是从栈底到栈顶数据是从大到小。
  • 单调递减栈:单调递减栈就是从栈底到栈顶数据是从小到大。
现在有一组数 $10,\ 3,\ 7,\ 4,\ 12$。从左到右依次入栈,则如果栈为空或入栈元素值小于栈顶元素值,则入栈;否则,如果入栈则会破坏栈的单调性,则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。
1. $10$入栈时,栈为空,直接入栈,栈内元素为 $10$。
2. $3$ 入栈时,栈顶元素 $10$ 比 $3$ 大,则入栈,栈内元素为 $10,\ 3$。
3. $7$ 入栈时,栈顶元素 $3$ 比 $7$ 小,则栈顶元素出栈,此时栈顶元素为 $10$,比 $7$ 大,则 $7$ 入栈,栈内元素为 $10,\ 7$。
4. $4$ 入栈时,栈顶元素 $7$ 比 $4$ 大,则入栈,栈内元素为 $10,\ 7,\ 4$。
5. $12$ 入栈时,栈顶元素 $4$ 比 $12$ 小,$4$ 出栈,此时栈顶元素为 $7$,仍比 $12$ 小,栈顶元素 $7$ 继续出栈,此时栈顶元素为 $10$,仍比 $12$ 小,$10$ 出栈,此时栈为空,$12$ 入栈,栈内元素为 $12$。


【问题】
给 $n$ 个整数,从左到右一次入栈,请维护一个单调递减栈。

Input

第一行一个整数 $n\ (1 \leq n \leq 100)$。
第二行有 $n$ 个整数, 第 $i$ 个整数为 $a_i\ (-10^9 \leq a_i \leq 10^9)$,表示第 $i$ 个进入堆栈的数 $a_i$。

Output

$n$ 行,每行若干个整数,第 $i$ 行表示第 $i$ 个数据 $a_i$ 入栈后,单调栈内从栈顶到栈底所有元素。

Sample 1 Input

5
10 3 7 4 12

Sample 1 Output

10
10 3
10 7
10 7 4
12

Sample 2 Input

8
10 3 3 7 4 4 4 12

Sample 2 Output

10 
10 3 
10 3 3 
10 7 
10 7 4 
10 7 4 4 
10 7 4 4 4 
12 

Source/Category

数据结构 2.3.单调栈