Skip to content

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 a[300000],queue[300000],head,tail=-1,n,k;
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){
        while (queue[head]<=i-k) head++;
        while (a[i]>=a[queue[tail]]&&tail>=head) tail--;
        queue[++tail]=i;
        printf("%d ",a[queue[head]]);
    }
    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;
}