综合补全:窗口最小队尾
补全 window_min 的队尾维护,输出每个窗口的最小值。 综合:按题目选单调栈(最近更值)还是单调队列(滑窗最值)。 (本题用 g++ -std=c++17 -O0 编译。)
对拍时暴力解法干什么用
用随机数据「对拍」时,那个又慢又简单的暴力解法的作用是【0】。
写下一个更大元素
场景:实验机上 ~/work/mono/nge.cpp 读入一个数组,要输出每个数右边第一个严格更大的数,可 next_greater 还是空的。 任务:补全 next_greater(用单调栈,没有更大的输出 -1)。make 编译(带内
五十万个数的滑窗最大
场景:~/work/mono/wmax.cpp 求所有长度为 k 的窗口的最大值之和,结果是对的,可 n = 50 万、k 很大时要跑十几秒。 任务:改写 wmax.cpp,让 n = 50 万也能在 1 秒内算完。make 编译(-O2)
能随时取最大值的队列
场景:~/work/mono/mq.cpp 要实现一个先进先出的队列,还要能随时 O(1) 输出队里的最大值,可 push、pop 还没写完。 任务:补全 MaxQueue 的 push 和 pop。make 编译(带内存检查)后用 sam
修好重复值的窗口最大
场景:~/work/mono/dup.cpp 求每个窗口的最大值,队列里存的是值。数都不一样时是对的,一有重复值就错。 任务:找出并修好出错的那个条件。make 编译(带内存检查)后用 sample.txt 自测;check 会用大量重复值
修好最大矩形的收尾
场景:~/work/mono/rect.cpp 求柱状图最大矩形,有的数据对,1 2 3 4 这种一路变高的却算小了。 任务:修好 largest_rect,让扫描结束时栈里剩下的柱子也被结算。make 编译(带内存检查)后用 sample
找出错误解法的反例
场景:~/work/mono/wrong.cpp 是一个「只看单根柱子和相邻两根柱子」的最大矩形算法,很多数据上它都是对的。 任务:按 ~/题目.txt 的要求(柱子根数、第一根的高度)构造一个让它算错的输入,写进 ~/work/mono/
重定向进来的是什么
「< 文件」把文件内容接到程序的标准输入 文件 程序 一行结果 程序照常读输入,读到文件末尾就结束 在终端里用 python3 stat.py < in.txt 运行,程序里读 sys.stdin 读到的是【0】。
第一行那个井号叹号
脚本第一行写 #!/usr/bin/env python3,它的作用是【0】。