Mike is the president of country What-The-Fatherland. There are n n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 1 to n n from left to right. i -th bear is exactly ai feet high.
A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strength of a group is the minimum height of the bear in that group.
Mike is a curious to know for each x x such that 1<=x<=n the maximum strength among all groups of size x .
The first line of input contains integer n (1<=n<=2×10 ^5), the number of bears.
The second line contains n n integers separated by space,a1,a2,…,an(1<=ai <=10 ^9), heights of bears.
输出格式：
Print n n integers in one line. For each x x from 1 1 to n n , print the maximum strength among all groups of size x .
题意：有一个长度为n的序列，序列有长度为1…n的连续子序列，一个连续子序列里面最小的值称作这个子序列的子序列的strength，
要求出每种长度的连续子序列的最大的strength。
思路：可以用单独栈求出每个点的L[i]，R[i]，以当前点为最小值的左右边界
然后排序一遍（按值排序）时间复杂度为排序复杂度（nlogn)
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int L[maxn], R[maxn], a[maxn]; stack<int> s; struct node { int w, len; }b[maxn]; int ans[maxn]; bool cmp(node a, node b) { return a.w > b.w; } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } a[0] = 0; a[n + 1] = 0; for (int i = 1; i <= n + 1; i++) { //处理右边界 while (!s.empty() && a[s.top()] > a[i]) { R[s.top()] = i - 1; s.pop(); } s.push(i); } while (!s.empty()) { s.pop(); } for (int i = n; i >= 0; i--) { //处理左边界 while (!s.empty() && a[s.top()] > a[i]) { L[s.top()] = i + 1; s.pop(); } s.push(i); } for (int i = 1; i <= n; i++) { b[i].w = a[i]; b[i].len = R[i] - L[i] + 1; } sort (b + 1, b + n + 1, cmp); //按大小排序 int cnt = 1; for (int i = 1; i <= n; i++) { int len = b[i].len; for (cnt; cnt <= b[i].len; cnt++) { // ans[cnt] = b[i].w; } } for (int i = 1; i <= n; i++) { printf("%d ", ans[i]); } return 0; }
