Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

数据结构——单调栈

2022/03/08 数据结构
Word count: 4,879 | Reading time: 23min

秋季PAT的第一题就是单调栈，之前没怎么学过， 因此这次专门学习做下笔记。

单调栈Monotone Stack

概念:

从行为上看，它不仅仅是用存储与访问受限的栈，而是一种辅助工具，用于检测数据的单调性变化并作出反应（表现: 当入栈元素会影响栈总体单调性时，要出栈一些元素以维持单调性）

场景：

  • 向左or向右找到第一个稍大（小）的元素、其索引下标；
  • 确定某条件（单调）下的最长区间；
  • 确定区间构成的极值，如max f（la，b]）；

Point：

单调递增栈: 指栈内元素的出栈序列递增（或递减），而栈内元素是递减（或递增），即当元素比栈顶小的时候入栈。因此需要输出下一个最大的元素。

当然也有人是直接根据栈内元素大小关系来区别， 比如栈内元素递减就叫做递减栈。

此外没有双向栈的存在。

==>2021年10月26日——明确下定义：单调递减栈为出从栈底往栈顶看，元素大小成递减排列。其实上，正确的理解应该从扫描的角度来看，比如从左往右扫描时，如果元素依次递减，则统统会入栈，e.g. [4,2,1,5,8], ==> 当5入栈时，单调递减的栈[4,2,1]横过来看就是原列表单调递减的子序列。

归纳：

  • 当从左往右扫描维护单调递减栈时，可以求元素左边第一个比他大的元素，也可以求右边第一个比它大的元素
    • 左边第一个比他大的元素：当以入栈元素的角度看时，如果栈内元素一直比它小，则不断pop，直到pop不出去元素，那么剩下的栈顶元素就是左边第一个比它大的元素
    • 右边第一个比它大的元素：当以栈内元素的角度看时，把他pop出去的入栈元素就是当前栈顶元素右边第一个比它大的元素

可见：从不同的角度看，能得到不同的效果，代码编写的区别在于ans数组的更新：一个在while不断pop的过程中更新（栈内被弹走元素的角度），另一个是while到pop停下后更新（入栈元素的角度）。

实际上，左边第一个大的元素和右边第一个大的元素是等价的，因为当从左往右扫描时求右边第一个大的元素问题，当吧原序列翻转（或是从右往左扫描时），得到的结果就是对原序列而言每个数左边第一个大的元素。

核心思想

在元素Y入栈的时候会跟栈顶元素X比较， 如果Y比栈内所有元素Xs都大的话，就可以拿到栈里所有的元素即区间。关键是这个比较， 就可以找到第一个满足要求的数据。

e.g.有列表[1, 3, 2, 0, 7]，从左向右遍历，当遍历为7时栈里有[3, 2, 0]，此时入栈元素为7， 能得到==>那么对于0来说，右边最大的就是当前入栈元素7， 左边最小的就是栈内下一个元素2。而对3来说，此时3上边的元素就都是比3小的元素们。

Code模板：

1
2
3
4
5
6
7
8
9
def getFirstMax(nums: List[int]):
    # 站内元素递减栈， 输出序列递增
    stack = []
    for i in range(len(nums) - 1, -1, -1):
        val = nums[i]
        if stack and val > stack[-1]:
            stack.pop()
        # 入栈操作在之前逻辑都执行完之哦吼，最后再入栈
        stack.append(val)

这种写法， 主要是运用的stack.pop元素

例题

Leetcode#496：

单调栈

Leetcode #496. 下一个更大元素 I

1
2
3
4
5
6
7
8
9
10
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        hash_dict = dict()
        stack = []
        for i in nums2:
            while stack and i > stack[-1]:
                # 在原有序列中比栈顶元素大的就是当前入栈元素i
                hash_dict[stack.pop()] = i
            stack.append(i)
        return [hash_dict.get(i,-1) for i in nums1]

Leetcode#962. 最大宽度坡：

单调栈

Q： 为什么想到了单调栈？

A：参看题解：首先把A数组中的以A[0]开头的递减序列抽取出来，我们最后要求的最大的宽度坡一定是以这个序列中的某一个i为坡底的，我们反证一下

假设存在某个元素位置k不存在于上面的递减序列中，且有最大宽度j-k，这也就说明k位置的元素一定是小于k前面所有的元素的，否则就会有更长的宽度，但是既然k小于前面所有的元素，那么k就一定会被加入到序列中，与假设矛盾，所以不存在k，解一定存在递减序列中

这样的话我们可以逆向遍历数组，每次遇到元素大于栈顶的就可以计算宽度，然后将栈顶弹出，因为是逆序遍历的，所以这个宽度一定是栈顶这个坡底i能形成的最大宽度了， 逆序遍历再往前的话即使大于这个栈顶，形成的宽度也只会减小，所以这个栈顶是可以直接pop出去的，我们遍历所有的坡底求最大值就行了，时间复杂度O(N)

作者：resolmi https://leetcode-cn.com/problems/maximum-width-ramp/solution/java-dan-diao-zhan-er-fen-jie-fa-chang-shi-jie-shi/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * @Author: Mrli
 * @Date: 2020-09-14 10:16:57
 * @LastEditTime: 2020-09-14 11:03:29
 * @Description: 
 */
#include <bits/stdc++.h>
using namespace std;

int maxWidthRamp(vector<int>& A) {
    stack< int > st;
    int len = A.size();
    // 维护一个递减栈
    for (int i = 0; i < len; i++) {
        if (st.empty() || A[i] <= A[st.top()]) st.push(i);
    }
    
    int ans = 0;
    int i = len - 1;
    while( i > ans){
        // 根据单调栈的含义， 此时入栈A[i]， 可以得到 st.top() 右边比其大的为A[i]， 同时栈里也都是比A[i]小的元素
        while( !st.empty() && A[st.top()] <= A[i] ){
            // printf("A[%d]:%d A[%d]:%d\n", st.top(), A[st.top()], i, A[i] );
            ans = max(ans, i - st.top());
            st.pop();
        }
        i --;
    }
    return ans;
}
    
int main(){
    vector<int> A = {6,0,8,2,1,5};
    int ans = maxWidthRamp(A);
    cout <<ans <<endl;
    return 0;
}

Leetcode#1124：

前缀和+单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

int longestWPI(vector<int>& hours) {
    int len = hours.size();
    // hash
    for(int i = 0; i < len; i ++ ){
        if ( hours[i] > 8) hours[i] = 1;
        else hours[i] = -1;
    }
    // 1, 1, -1, -1, -1, -1, 1
    vector<int> sum(len + 1, 0);
    for(int i = 1; i <= len; i++ ){
        sum[i] = sum[i - 1] + hours[i - 1];
    }
    stack<int> st;
    //  顺序生成单调栈，栈中元素从第一个元素开始严格单调递减，最后一个元素肯定是数组中的最小元素所在位置
    for(int i = 0; i <= len; i++ ){
        if ( st.empty() || sum[i] < sum[st.top()]) 
            st.push(i);
    }
    
    
    int ans = 0;
    /** 常规写法： */
    for (int i = len; i >= 0 ; i--) {
        while( !st.empty() && sum[st.top()] < sum[i]){
            ans = max(ans, i - st.top());
            st.pop();
        }
    }
    
    /** 写法二: */
    int i = len;
    //  倒序扫描数组，求最大长度坡
    while( i > ans){
        // sum[st.top()] < sum[i]实际就是找到 sum > 0, 即后面索引j的sum - 前面索引i的sum > 0
        while( !st.empty() && sum[st.top()] < sum[i]){
            ans = max(ans, i - st.top());
            st.pop();
        }
        i -= 1;
    }
    return ans;
}
    
int main(){
    vector<int> A = {9,9,6,0,6,6,9};
    int ans = longestWPI(A);
    cout <<ans <<endl;
    return 0;
}
// 此题单调栈具体怎么来的可以看题解： https://leetcode-cn.com/problems/longest-well-performing-interval/solution/can-kao-liao-ji-ge-da-shen-de-ti-jie-zhi-hou-zong-/

参看：Bilibili【带写03】python前缀和与单调栈.mp4

单调队列

P1886 滑动窗口 /【模板】单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

// 这个写法可以借鉴一下
struct node{
    int val;
    int id;	        // 下标
};

vector<int> v1; // 最小
vector<int> v2; // 最大

int n, k;
deque<node> q1;
deque<node> q2;


int main(){
    cin >> n >> k;
    int val;
    for (int i = 1; i <= n; i++) {
        node nd;
        cin >> nd.val;
        nd.id = i;
        
		// 如果当前元素小于栈顶元素， 则栈顶元素出栈
        // -->获得栈顶小于当前预算
        while( !q1.empty() && nd.val <= q1.back().val){
             q1.pop_back();      
        }
        while( !q2.empty() && nd.val >= q2.back().val) q2.pop_back();
        q1.push_back(nd);
        q2.push_back(nd);
        if ( i - q1.front().id + 1 > k) q1.pop_front();                 // 如果栈底元素已经超出边界则出栈
        if ( i - q2.front().id + 1 > k) q2.pop_front();

        if (i >= k){        // 当索引满足窗口大小的时候才进行操作
            v1.push_back(q1.front().val);                  // 栈底元素为当前k窗口中最小的
            v2.push_back(q2.front().val);                  // 栈底元素为当前k窗口中最大的
        }
    }

    int len = v1.size();
    for (int i = 0; i < len; i++) {
       cout << v1[i] << " ";
    }
    cout << endl;
    len = v2.size();
    for (int i = 0; i < len; i++) {
       cout << v2[i] << " ";
    }
    return 0;
}

holiday

题目描述

经过几个月辛勤的工作，FJ决定让奶牛放假。

假期可以在1…N天内任意选择一段（需要连续），每一天都有一个享受指数W。但是奶牛的要求非常苛刻，假期不能短于P天，否则奶牛不能得到足够的休息；假期也不能超过Q天，否则奶牛会玩的腻烦。

FJ想知道奶牛们能获得的最大享受指数。

输入格式

第一行：N,P,Q.

第二行：N个数字，中间用一个空格隔开。

输出格式

一个整数，奶牛们能获得的最大享受指数。

样例数据

input

1
2
5 2 4
-9 -4 -3 8 -6

output

1
5

Hint 选择第3-4天，享受指数为-3+8=5。

数据规模与约定

50% 1≤N≤10000，100% 1≤N≤100000

时间限制：1s， 空间限制：256MB

思路：

用前缀和处理前i天的指数和
其实就是从P的位置开始枚举，每次把i-P压入队列，如果i-Q大于队首元素的位置，弹出队首
每次取出队首让ans=max（sum[i]-sum[Day.front()]）
最后输出ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define INF 9999999999
long long sum[100300];
int n,p,q;
long long ans=-INF;
deque<long long> Day;
 
int main(){
	freopen("holiday.in","r",stdin);
	// freopen("holiday.out","w",stdout);
	scanf("%d%d%d",&n,&p,&q);
	long long x;
    // 前缀和
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		sum[i]=sum[i-1]+x;
	}
    
	for(int i=p;i<=n;i++){
		int nowIndex = i - p;
        // 指数和小的放前面
		while(!Day.empty() && sum[nowIndex] < sum[Day.back()] ) Day.pop_back();
		Day.push_back(nowIndex);
        // 实际上应该理解为 当前日期i - 队首的日期 > Q天, 则让pop_front 
		while(!Day.empty() && i - q > Day.front())  Day.pop_front();
        // sum[i] - sum[Day.front()]  为索引i~Day.front()这几天的指数和
		ans=max(ans, sum[i]-sum[Day.front()]);
	}
	cout<<ans;
	return 0;
}

总结: 单调队列对于处理线性滑动区间最值可谓游刃有余

借鉴: 数据结构之单调队列与单调栈

单调栈

P2866 [USACO06NOV]Bad Hair Day S

根据题目细品: 第N头牛站最前面, 第1头站最后面, 然后如果Hi > Hn, 则能看到。要求累加第i头牛能看到前面牛的头发数， 即可以理解为第i头牛往前看， 找到比它大的Hi或者边界（边界可以看做为Hi=0的）。===> 输入样例从左往右找比当前元素大的第一个元素，单调递减栈–>正常for i = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f;

int n;
struct cow{
    int id;
    int height;
};
stack<cow> st;
int main(){
    int tmp;
    int ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        // C_i的高度
       cin >> tmp;
       // 找到比当前元素大的一个元素， 期间小的都累计
       while( !st.empty() && tmp >= st.top().height ) {
           ans += ( i - st.top().id - 1);
           st.pop();
       }
       st.push({i, tmp});
    }
	// 到最后的时候， 剩下的递减的都是前面没有比自己高的牛了， 如样例最后剩5<-6， 那么6(2)前面没数字了， 所以为0， 5前面(12)只有6了，且6的2高<5的12高， 因此6-5=1有1头牛
    while(!st.empty()){
        int now = st.top().id;
        st.pop();
        ans += (n - now);
    }
    cout << ans <<endl;
    return 0;
}

思路2：

  1. 每次输入一头牛的身高，找比这头牛矮的，出栈
  2. 剩下的牛皆可以看到这只牛
  3. ans值加等于栈中牛的个数
  4. 这头牛入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n,t;
long long ans; //注意要开long long 
stack <int> a;
int main() {
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>t;
        // 将栈内删到全都是比t的高的
		while (!a.empty() && t >= a.top() )  
			a.pop();
		// 那么栈里的元素都能看到i
		ans+=a.size();
        // 注意： 先size后push
		a.push(t);
	}
	cout<<ans;
	return 0;
}

气温 列表 #739 每日温度

从左往右找比当前元素大的–>如果当前元素比栈顶元素大，那么栈顶元素右边比其第一个大的元素就是当前入栈元素—>单调递减栈（从栈底到栈顶递减）–>val > st.top()，正常for i = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int n;
int ans[maxn];  // 答案
struct temperature{
    int id;
    int tmp;
};
/**
input:
8
73 74 75 71 69 72 76 73
output:
1 1 4 2 1 1 0 0
*/
int main(){
    stack<temperature> st;
    cin >> n;
    int val;
    for (int i = 0; i < n; i++) {
       cin >> val ;
       while ( !st.empty() && val > st.top().tmp ){
           ans[st.top().id] = i - st.top().id ; 
           st.pop();
       }
       st.push({i, val});      // 塞进去的是索引
    }
    for (int i = 0; i < n; i++) {
       cout <<ans[i] << " ";
    }
    cout << endl;
    return 0;
}

逆序写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int n;
int ans[maxn];  // 答案
struct temperature{
    int id;
    int tmp;
    temperature(){}
    temperature(int _id, int _tmp): id(_id), tmp(_tmp){}
};
/**
input:
8
73 74 75 71 69 72 76 73
output:
1 1 4 2 1 1 0 0
*/
int main(){
    stack<temperature> st;
    cin >> n;
    int val;
    vector<int> v(n+1);
    for (int i = 1; i <= n; i++) {
       cin >> v[i];
    }
    for (int i = n; i >= 1; i--) {
        int val = v[i];
       while( !st.empty() && val >= st.top().tmp) st.pop();
        ans[i] = st.empty()? 0 : st.top().id - i;
        st.push(temperature(i, val));
    }
    for (int i = 0; i < n; i++) {
       cout <<ans[i] << " ";
    }
    cout << endl;
    return 0;
}

P5788 【模板】单调栈

模板写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// ▲不知道为啥必须点开洛谷的O2优化才不会被卡后面4个点
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int n;
int main(){
    scanf("%d", &n);
    vector<int> v;
    v.resize(n+1);
    stack< pair<int, int> > st;
    vector<int> ans(n+1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
       while( !st.empty() && v[i] > v[st.top().first]){
           ans[ st.top().first ] = i;
           st.pop();
       }
       st.push({i, v[i]});
    }
	// 遍历完的时候栈里其实还有元素
    // cout << "size: "<<st.size() << endl;
    for (int i = 1; i <= n; i++) {
        if ( i == 1) printf("%d", ans[i]);
        else printf(" %d", ans[i]);
    }
    return 0;
}

for遍历倒着写

1
2
3
4
5
6
7
8
//my
for (int i = n; i >= 1 ; i--) {
    while( !st.empty() && v[i] >= v[st.top().first]){
        st.pop();
    }
    ans[ i ] = st.empty() ? 0: st.top().first;
    st.push({i, v[i]});
}

// 找的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int n,a[3000001],b[3000001];
stack<int> q;//开一个STL的栈 栈里面存的是数的下标即位置
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>a[i];//输入
    for(int i=n;i>=1;i--){
        while(!q.empty() and a[q.top()]<=a[i])//查找第一个大于a[i]的数 
			q.pop();         //否则就直接出栈
		if(q.empty())        //如果最后没有比a[i]大的数
		   b[i]=0;
		else
        b[i]=q.top();        //否则就记录下来
        q.push(i);           //将i入栈
    }
    for(int i=1;i<=n;i++) cout<<b[i]<<" ";//输出答案 结束
   return 0;
}

区别在于： 站内元素是栈顶元素的右边； 而顺着写， 那么栈内元素是栈顶元素的左边， 即栈顶元素为站内元素的右边；同时还有一个区别是： 顺着先能边读边写， 而倒着写必须读完再写

不用v[]的写法, 其实直接可以用stack< pair<int, int> >st来写，可能会更直观一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int n;

int main(){
    int val;
    scanf("%d", &n);
    stack< pair<int, int> > st;
    vector<int> ans(n+1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &val);
       while( !st.empty() && val > st.top().second ){
           ans[ st.top().first ] = i;
           st.pop();
       }
       st.push({i, val});
    }

    for (int i = 1; i <= n; i++) {
        if ( i == 1) printf("%d", ans[i]);
        else printf(" %d", ans[i]);
    }
    return 0;
}

总结

单调栈可利用的点:

  • 剩下的元素 跟 当前元素的关系；弹出元素的个数；剩余元素的个数
  • 栈顶 和 当前元素的关系==> 找到第一个比数大、小的

递减栈的while中条件写 val > st.top()的时候pop，正着写和反着写都一样， 但是要注意等于号的区别；顺着写判断条件完全满足题意（利用pop的动作做处理），而逆着则要考虑先后，如气温题，找第一个反而要加等号， 要pop掉直到左边第一个出现。

===

一般情况下，都是写while()里只有pop的，nums[i] < nums[st.peek()]==>st.pop();，则是维护了一个单调递增栈，对于剩下的栈顶元素而言，入栈元素是>=栈顶元素的，并且对于入栈元素而言找到的是左边第一个大于他的数。单调递减栈，则求的是左边第一个比他小的数。 ===> 如果要求右边的，法一：逆序构建单调栈；法二：从栈顶元素的视角来看(赋值在while里面)，只不过这种做法最终栈里会有剩余元素，因此需要对记录数组赋初值。如：2055. 蜡烛之间的盘子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
   public int[] platesBetweenCandles(String s, int[][] queries) {
        int len = s.length();
        int[] arr = new int[len];

        // 当前元素前面拥有的*数
        for (int i = 1; i < len; i++) {
            char c = s.charAt(i - 1);
            if (c == '*') {
                arr[i] = arr[i - 1] + 1;
            } else {
                arr[i] = arr[i - 1];
            }
        }

        Stack<Integer> minSt = new Stack<>();
        Stack<Integer> maxSt = new Stack<>();

        // 右边下标最小的蜡烛
        int[] minRight = new int[len], maxLeft = new int[len];
       // 得赋初值
        Arrays.fill(minRight, len);
        Arrays.fill(maxLeft, -1);

       for (int i = 0; i < len; i++) {
           char c = s.charAt(i);

           // 如果当前是|则最近的就是自己
           if ( c == '|'){
               minRight[i] = i;
               maxLeft[i] = i;
           }

           // **得入栈
           while (!minSt.empty() && c == '|' && s.charAt(minSt.peek()) == '*') {
               minRight[minSt.peek()] = i;
               minSt.pop();
           }
           minSt.push(i);

           char ch = s.charAt(len - i - 1);
           while (!maxSt.empty() && ch == '|' && s.charAt(maxSt.peek()) == '*') {
               maxLeft[maxSt.peek()] = len - i - 1;
               maxSt.pop();
           }
           maxSt.push(len - i - 1);
       }


        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0], r = queries[i][1];
            int ll = minRight[l], rr = maxLeft[r];
            if (ll < rr) {
                ans[i] = arr[rr] - arr[ll];
            }else{
                ans[i] = 0;
            }
        }
        return ans;
    }
}

Author: Mrli

Link: https://nymrli.top/2020/09/08/数据结构——单调栈/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
docsify使用记录NextPost >
扇区、块/簇
CATALOG
  1. 1. 单调栈Monotone Stack
    1. 1.1. 概念:
    2. 1.2. 场景：
    3. 1.3. Point：
    4. 1.4. 核心思想
    5. 1.5. Code模板：
    6. 1.6. 例题
      1. 1.6.1. Leetcode#496：
      2. 1.6.2. Leetcode #496. 下一个更大元素 I
      3. 1.6.3. Leetcode#962. 最大宽度坡：
      4. 1.6.4. Leetcode#1124：
      5. 1.6.5. 单调队列
        1. 1.6.5.1. P1886 滑动窗口 /【模板】单调队列
        2. 1.6.5.2. holiday
      6. 1.6.6. 单调栈
        1. 1.6.6.1. P2866 [USACO06NOV]Bad Hair Day S
        2. 1.6.6.2. 气温 列表 #739 每日温度
        3. 1.6.6.3. P5788 【模板】单调栈
    7. 1.7. 总结