5755: 学习系列——单调栈 I——构建单调递减栈
[Creator : ]
Description
【知识点】
单调栈中存放的数据应该是有序的,所以单调栈也分为单调递增栈和单调递减栈
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$ 个整数,从左到右一次入栈,请维护一个单调递减栈。
单调栈中存放的数据应该是有序的,所以单调栈也分为单调递增栈和单调递减栈
- 单调递增栈:单调递增栈就是从栈底到栈顶数据是从大到小。
- 单调递减栈:单调递减栈就是从栈底到栈顶数据是从小到大。
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$。
第二行有 $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