文章目录
前言
今日acm训练单调栈，菜鸟进阶记录一下题解，代码肯定有不足之处，望斧正。
一、弟弟or哥哥？
Description
闲聊群里有一个初三的小哥哥，有的人觉得别人才初三，不应该叫他小弟弟吗？哈哈哈。
如果别人问的问题比较简单，那么他应该是一个弟弟。如果问的题我们解决不了那可能就得叫他哥哥了。对吧。
今天这位小“哥哥”又来问问题了。题是这样的：
有n座山，他们连在一起成一条直线，接着从左往右给出每座山的高度a[i]，现在的问题是让你求的每座山右边的第一个比它高的山是第几座山呢？如果没有则输出0
Input
测试数据有多组。对于每组测试数据：
输入一个n表示有n座山（1 <= n <= 1000000）
接着输入n个数a[i] （ 1 <= a[i] <= 1000000），表示第i座山的高度。
Output
对于每组测试数据输出每座山右边的第一个比它高的山是第几座山？如果没有则输出0
Sample Input Copy
5
1 2 3 4 5
3
1 1 1
Sample Output Copy
2 3 4 5 0
0 0 0
#include <iostream>
#include <stack>
using namespace std;
int a[100010], b[100010];
stack<int> q;
int main()
{
int n;
while (scanf("%d", &n) != EOF) {
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
while (!q.empty() && a[i] > a[q.top()]) {
b[q.top()] = i;
q.pop();
}
q.push(i);
}
while (!q.empty()) {
b[q.top()] = 0;
q.pop();
}
for (int i = 1; i <= n; i++) {
printf("%d ", b[i]);
}printf("\n");
}
return 0;
}
二、田径场上的字符串
Description
给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件：原字符串中出现的字符，新字符串也必须包含。 新字符串中所有的字符均不相同。新字符串的字典序是满足上面两个条件的最小的字符串。
Input
多组输入：
仅一行，有一个只含有可打印字符的字符串 s。长度小于等于1e5
Output
在一行输出字典序最小的新字符串。
Sample Input Copy
4444555666
Sample Output Copy
456
HINT
字符串中包含空格
#include<iostream>
#include<string>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;
int vis[100010], str[100010];
string s;
int main() {
while (getline(cin, s)) {
memset(vis, 0, sizeof(vis));
memset(str, 0, sizeof(str));
stack<char>st;
for (int i = 0; i < s.size(); i++) {
str[s[i]]++;
}
for (int i = 0; i < s.size(); i++) {
str[s[i]]--;
if (st.empty() || st.top() < s[i] && !vis[s[i]]) {
st.push(s[i]);
vis[s[i]] = 1;
}
else {
if (!vis[s[i]]) {
while (!st.empty() && st.top() > s[i] && str[st.top()] > 0) {
vis[st.top()] = 0;
st.pop();
}
st.push(s[i]);
vis[s[i]] = 1;
}
}
}
vector<char>vc;
while (!st.empty()) {
vc.push_back(st.top());
st.pop();
}
for (int i = vc.size() - 1; i >= 0; i--) {
printf("%c", vc[i]);
}
printf("\n");
while (!st.empty())
st.pop();
vc.clear();
}
return 0;
}
三、 田径场上的ZYS
Description
夏季到了，又到了露胳膊，露腿的季节。每天晚上zys都会去田径场跑步锻炼身体，为的就是“穿衣显瘦，脱衣有肉”。他说跑的太快对身体不好，所以他不想跑的太快了，但是他又不想跑的太慢了。现在田径场上有一队小姐姐排成一列，在跑步，人数为N，每人速度为V。zys就想在这列小姐姐旁边跑步，顺便liaolaio.已经知道zys最多可以交流的小姐姐数为M。为了方便交流，zys需要提前知道每个M区间小姐姐的最大速度与最小速度。
为了方便计算，一列小姐姐不会形成环
Input
多组输入：
第一行输入：N<=1e6，M<=N
第二行输入N个V； 0<V<=1e5
Output
按顺序输出N-M+1行
每行表示长度为M的区间的小姐姐的最大速度与最小速度。
Sample Input Copy
10 3
6 4 10 10 8 6 4 2 12 14
Sample Output Copy
4 10
4 10
8 10
6 10
4 8
2 6
2 12
2 14
#include<iostream>
#include<deque>
using namespace std;
int a[1000005];
int m[1000005];
int ii[1000005];
int main()
{
int n, k;
int j = 0;
deque<int> s;
while (scanf("%d%d", &n, &k) != EOF) {
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
s.push_back(1); j = 0;
for (int i = 2; i <= n; i++) {
while (!s.empty() && a[i] > a[s.back()])
s.pop_back();
s.push_back(i);
if (i >= k) {
while (!s.empty() && s.front() <= i - k)
s.pop_front();
m[j] = a[s.front()]; j++;
}
}
s.clear();
s.push_back(1); j = 0;
for (int i = 2; i <= n; i++) {
while (!s.empty() && a[i] < a[s.back()])
s.pop_back();
s.push_back(i);
if (i >= k) {
while (!s.empty() && s.front() <= i - k)
s.pop_front();
ii[j] = a[s.front()]; j++;
}
}
for (int i = 0; i < n - k + 1; i++) {
printf("%d %d\n", ii[i], m[i]);
}
s.clear();
}
return 0;
}