# 11541: 【原1541】区间最大问题

### 题目描述

author: 林泽冰 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1541

## Description

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

(This is the problem B for SEIEE-Yu Yong Data Structure 2015 Fall Exam 2)

## Input Format

3 rows, the first rows is a number k and the second rows is a number n.

The third row is n numbers separated by a blank.

## Output Format

n-k+1 numbers in a row separated by a blank.

## Sample Input

``````3
8
1 3 -1 -3 5 3 6 7
``````

## Sample Output

``````3 3 5 5 6 7
``````

## Data Range

50% : n < 1000

100% : n < 200000, k<n, all number is in the range of longint.

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "set"
using namespace std;

int main() {
int k, n;
cin >> k >> n;

multiset<int,greater<int>> mySet;

int currentNum,*numData=new int[n];
for (int i = 0; i < k; i++) {
int tempNum;
scanf("%d", &tempNum);
numData[i] = tempNum;
}

mySet.insert(numData, numData + k);
cout << *mySet.begin();
for (int startNum = 0; startNum + k < n; startNum++) {
int tempNum;
scanf("%d", &tempNum);
numData[startNum + k] = tempNum;
mySet.erase(mySet.find(numData[startNum]));
mySet.insert(tempNum);
printf(" %d", *mySet.begin());
}
return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 200000 + 100;

int k, n;
long long nums[maxN] = {0}, maxNums[maxN] = {0};

class deque {
private:
int data[maxN];
int f, b;

public:
deque() : f(0), b(0) {}

void push_front(int &x) {
data[f] = x;
f += (maxN - 1);
f %= maxN;
}

void push_back(int &x) {
b = (b + 1) % maxN;
data[b] = x;
}

int front() { return data[(f + 1) % maxN]; }

int back() { return data[b]; }

int pop_front() {
f = (f + 1) % maxN;
return data[f];
}

int pop_back() {
int temp = data[b];
b += (maxN - 1);
b %= maxN;
return temp;
}

bool is_empty() { return f == b; }
};

int main() {
deque maxNum;

cin >> k >> n;

for (int i = 1; i <= n; i++) {
cin >> nums[i];
}

for (int i = 1; i <= n; i++) {
while (!maxNum.is_empty() && nums[i] > nums[maxNum.back()]) {
maxNum.pop_back();
}

if (!maxNum.is_empty() && i - maxNum.front() >= k) {
maxNum.pop_front();
}

maxNum.push_back(i);
maxNums[i] = nums[maxNum.front()];
}

for (int i = k; i <= n; i++) {
cout << maxNums[i] << ' ';
}

return 0;
}
``````

## q4x3's solution

``````/**
* 区间最大问题
* 拿线段树混的
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define ll long long

const int MAXN = 2e5 + 233;
ll dt[MAXN], tree[MAXN << 2];
int k, n;

ll maxx(ll x, ll y) {
return x > y ? x : y;
}

void build(int l, int r, int rt) {
if(l == r) {
tree[rt] = dt[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
tree[rt] = maxx(tree[rt << 1], tree[rt << 1 | 1]);
}

ll query(int rt, int l, int r, int s, int t) {
if(s <= l && t >= r) return tree[rt];
int mid = (l + r) >> 1;
if(t <= mid) return query(rt << 1, l, mid, s, t);
else if(s > mid) return query(rt << 1 | 1, mid + 1, r, s, t);
else return maxx(query(rt << 1, l, mid, s, t),
query(rt << 1 | 1, mid + 1, r, s, t));
}

int main() {
scanf("%d%d", &k, &n);
for(int i = 1;i <= n;++ i)
scanf("%lld", &dt[i]);
build(1, n, 1);
for(int i = 1;i <= n - k + 1;++ i)
printf("%lld ", query(1, 1, n, i, i + k - 1));
printf("\n");
}
``````

## victrid's solution

``````#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
long long nums[200010];
long long st[200010][25];
inline int lg(int n) { return n ? lg(n / 2) + 1 : -1; }
int main() {
int n, k, lgk;
scanf("%d%d", &k, &n);
lgk = lg(k);
for (int i = 1; i <= n; i++) {
scanf("%lld", &nums[i]);
st[i][0] = i;
}
for (int j = 1; j <= lgk; j++) {
for (int i = 1; i <= n; i++) {
st[i][j] = nums[st[i][j - 1]] > nums[st[i + (1 << (j - 1))][j - 1]] ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
}
}
for (int i = 1; i <= n - k + 1; i++) {
if (i - 1)
printf(" ");
printf("%lld", max(nums[st[i][lgk]], nums[st[i + k - (1 << lgk)][lgk]]));
}
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
using namespace std;
int main() {
scanf("%d%d",&k,&n);
for (int i=0;i<n;++i) scanf("%d",&a[i]);
for (int i=0;i<k-1;++i)
{
while (a[i]>=a[queue[tail]]&&tail>=0) tail--;
queue[++tail]=i;
}
for (int i=k-1;i<n;++i){
queue[++tail]=i;
}
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 200010;
struct node {
int l, r, key;
}tree[MAX_N << 2];

void maketree(int node, int l, int r) {

if (l == r) {
cin >> tree[node].key;
tree[node].l = l; tree[node].r = r;
return;
}
int mid = (l + r) >> 1;
maketree(node << 1, l, mid);
maketree(node << 1 | 1, mid + 1, r);
tree[node].l = l; tree[node].r = r;
tree[node].key = max(tree[node << 1].key, tree[node << 1 | 1].key);
}

int query(int node, int l, int r) {

if (tree[node].l == l && tree[node].r == r) return tree[node].key;
int mid = (tree[node].l + tree[node].r) >> 1;
if (r <= mid) return query(node << 1, l, r);
else if (l > mid) return query(node << 1 | 1, l, r);
else return max(query(node << 1, l, mid), query(node << 1 | 1, mid + 1, r));
}

int main() {

ios::sync_with_stdio(false);
int k, n;
cin >> k >> n;
maketree(1, 1, n);
for (int i = 1; i <= n - k + 1; ++i) cout << query(1, i, i + k - 1) << " ";
return 0;
}
``````