单调栈结构(进阶)_

C/C++

infiniteft

栽cin和cout的坑里了，同一套代码，用cin和cout 进行IO超时了，用scanf,printf 通过了

通过的代码：

#include<iostream>
#include<stack>
#include<vector>

using namespace std;
int main(void)
{
    int n = 0, num;
    cin >> n;
    stack<int> stk;
    vector<vector<int>> ret(n);
    vector<int> nums(n);
    for(int i = 0; i < n; i++)
    {
        cin >> num;
        nums[i] = num;
        while(!stk.empty() && nums[stk.top()] >= num)
            stk.pop();
        if(stk.empty())
            ret[i] = vector<int>{-1, -1};
        else
            ret[i] = vector<int>{stk.top(), -1};
        stk.push(i);
    }
    while(!stk.empty())
    {
        stk.pop();
    }
    for(int i = n - 1; i >= 0; i--)
    {
        while(!stk.empty() && nums[stk.top()] >= nums[i])
            stk.pop();
        if(stk.empty())
            ret[i][1] = -1;
        else
            ret[i][1] = stk.top();
        stk.push(i);
    }
    for(int i = 0; i < n; i++)
    {
        cout << ret[i][0] << " " << ret[i][1] << endl;
    }
}

超时代码

#include<iostream>
#include<stack>
#include<vector>
#include<cstdio>

using namespace std;
int main(void)
{
    int n = 0;
    cin >> n;
    stack<int> stk;
    vector<vector<int> > ret(n,{-1,-1});
    vector<int> nums(n);
    for(int i = 0; i < n; i++)
    {
        cin >> nums[i];
        while(!stk.empty() && nums[stk.top()] >= nums[i])
            stk.pop();
        if(!stk.empty())
            ret[i][0] = stk.top();
        stk.push(i);
    }
    while(!stk.empty())
    {
        stk.pop();
    }
    for(int i = n - 1; i >= 0; i--)
    {
        while(!stk.empty() && nums[stk.top()] >= nums[i])
            stk.pop();
        if(!stk.empty())
            ret[i][1] = stk.top();
        stk.push(i);
    }
    for(int i = 0; i < n; i++)
    {
        cout <<ret[i][0] << " " << ret[i][1] << endl;
    }
}

发表于 2019-11-05 23:30:10 回复(4)

天命剑主

//
// Created by yuanhao on 2019-8-30.
//

#include <iostream>

using namespace std;

// 可以用两个栈分两次做，这样只能过75%数据，
// 如果用一次循环，使用stl的stack<pair<int,int>>，可以过95%，
// 要想过100%，还得自己手写栈提高速度，而且不要用pair，对象多了也会耗时间。。。
// 没办法，为了考察出两倍的时间差异，这道题对时间卡得比较死
int main() {
    int n = 0;
    cin >> n;
    int numbers[n];
    int l_res[n];
    int r_res[n];
    for (int i = 0; i < n; ++i) {
        cin >> numbers[i];
    }
    int stack[n * 2]; // 栈，保存数字下标和数字，两个元素为一个帧
    int top = 0; //栈顶指针
    for (int i = 0; i < n; ++i) {
        while (top != 0 && numbers[i] < stack[top - 1]) {
            r_res[stack[top - 2]] = i;
            top -= 2;
        }
        if (top == 0) {
            l_res[i] = -1;
        } else {
            if (numbers[i] == stack[top - 1]) {
                l_res[i] = l_res[stack[top - 2]];
            } else {
                l_res[i] = stack[top - 2];
            }
        }
        stack[top++] = i;
        stack[top++] = numbers[i];
    }
    while (top != 0) {
        r_res[stack[top - 2]] = -1;
        top -= 2;
    }

    for (int i = 0; i < n; ++i) {
        printf("%d %d\n", l_res[i], r_res[i]);
    }

    return 0;
}

发表于 2019-08-30 16:55:24 回复(0)

ac_q

头条一面没写出来，现在运行不出来

#include 
(849)#include 
#include 
using namespace std;
int main()
{
    int n = 0;
    cin >> n;
        vector nums(n);
        for (int i = 0; i < n; i++)
        {
            cin >> nums[i];
        }
        vector prevs(n, -1);
        vector nexts(n, -1);
        stack s;
        s.push(0);
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[s.top()] <= nums[i])
            {
                prevs[i] = s.top();
                s.push(i);
            }
            else
            {
                while (!s.empty() && nums[s.top()] > nums[i])
                {
                    s.pop();
                }
                if (!s.empty())
                {
                    prevs[i] = s.top();
                }
                s.push(i);
            }
        }
        s.push(n - 1);
        for (int i = n - 2; i >= 0; i--)
        {
            if (nums[i] < nums[s.top()])
            {
                s.push(i);
            }
            else
            {
                nexts[i] = s.top();
            }
        }
        for (int i = 0; i < n; i++)
        {
            cout << prevs[i] << " " << nexts[i] << endl;
        }
}

发表于 2020-05-09 00:03:08 回复(0)

C/C++

圣光天启

#include <stdio.h>
#include <stdlib.h>

/* 用函数挨个跑他不香嘛*/
int l(int a[],int i,int n)
{
    int j=i;
    for(i;i>=0;i--)
    {
        if(i==0&&a[i]>a[j])
        return -1;
        else if(a[i]<a[j])
        return i;
    }
        return -1;
}
int r(int a[],int i,int n)
{
    int j=i;
    for(i;i<n;i++)
    {
        if(i==n-1&&a[i]>a[j])
        return -1;
        else if(a[i]<a[j])
        return i;
    }
        return -1;
}
int main(int argc, char *argv[]) {
    int n;
    scanf("%d",&n);
    int arr[n];
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
     }
     for(i=0;i<n;i++)
     {
         printf("%d %d\n",l(arr,i,n),r(arr,i,n));
     }
    return 0;

}

发表于 2019-11-22 09:14:02 回复(0)

鱼田

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int left, right;
};

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> a;
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }

    vector<node> nn(n);
    for (int i = 0; i < n; i++)
    {
        nn[i].left = -1;
        nn[i].right = -1;
    }

    nn[0].left = -1;
    for (int kk = 1; kk < a.size(); kk++)
    {
        if (a[0] > a[kk])
        {
            nn[0].right = kk;
            break;
        }
    }

    nn[a.size() - 1].right = -1;
    for (int kk = a.size() - 2; kk >= 0; kk--)
    {
        if (a[a.size() - 1] > a[kk])
        {
            nn[a.size() - 1].left = kk;
            break;
        }
    }

    for (int i = 1; i < a.size() - 1; i++)
    {

        for (int jj = i - 1; jj >= 0; jj--) /*left*/
        {
            if (a[jj] < a[i])
            {
                nn[i].left = jj;
                break;
            }
        }

        for (int kkk = i + 1; kkk < a.size(); kkk++)/*right*/
        {
            if (a[i] > a[kkk])
            {
                nn[i].right = kkk;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout << nn[i].left << " " << nn[i].right << endl;
    }
    return 0;
}

75% 纯数组写的

发表于 2019-09-09 13:44:56 回复(0)

11111111343e

#include <vector>
#include <iostream>
#include <stack>
#include <stdio.h>
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> datas(n);
	vector<int> Lres(n, -1);
	vector<int> Rres(n, -1);
	stack<int> arrdeq;
	for (int i = 0; i < n; i++) {
		scanf("%d", &datas[i]);
		while (!arrdeq.empty() && datas[arrdeq.top()] >= datas[i]) {
			arrdeq.pop();
		}
		if (!arrdeq.empty()) {
			Lres[i] = arrdeq.top();
		}
		arrdeq.push(i);
	}
	stack<int> arrdeq2;
	for (int i = n - 1; i >= 0; i--) {
		while (!arrdeq2.empty() && datas[arrdeq2.top()] >= datas[i]) {
			arrdeq2.pop();
		}
		if (!arrdeq2.empty()) {
			Rres[i] = arrdeq2.top();
		}
		arrdeq2.push(i);
	}


	for (int i = 0; i < n; i++) {
		printf("%d %d\n", Lres[i], Rres[i]);
	}
	return 0;
}

发表于 2019-08-10 15:37:27 回复(3)

Java

牛客196305255号

注意避免输出IO引起的低效率

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner  sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        int[][] res=new int[n][2];
        Deque<Integer> stack=new ArrayDeque<>();
        for(int i=0;i<n;i++){
            int tmp=sc.nextInt();
            arr[i]=tmp;
            while(!stack.isEmpty()&&arr[stack.peek()]>=tmp){
                stack.pop();
            }
            if(stack.isEmpty())
                 res[i][0]=-1;
            else
                res[i][0]=stack.peek();
            stack.push(i);
        }
        stack.clear();
        for(int i=arr.length-1;i>=0;i--){
             while(!stack.isEmpty()&&arr[stack.peek()]>=arr[i]){
                stack.pop();
            }
            if(stack.isEmpty())
                 res[i][1]=-1;
            else
                res[i][1]=stack.peek();
            stack.push(i);
        }
        StringBuilder sb=new StringBuilder();
        for(int[] t:res){
            sb.append(t[0]).append(" ").append(t[1]).append("\n");
        }
        System.out.println(sb.toString());
        sc.close();
    }
}

发表于 2021-04-07 12:54:01 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n], l[n], r[n];
    stack<int> S;
    for(int i=0;i<n;i++){
        cin>>a[i];
        l[i] = r[i] = -1;
    }
    for(int i=0;i<n;){
        if(S.empty()){
            S.push(i++);
        }else if(a[i]>=a[S.top()]){
            if(a[i] == a[S.top()])
                l[i] = l[S.top()];
            else
                l[i] = S.top();
            S.push(i++);
        }else{
            r[S.top()] = i;
            S.pop();
        }
    }
    for(int i=0;i<n;i++)
        printf("%d %d\n", l[i], r[i]);
    return 0;
}

发表于 2020-05-31 01:35:23 回复(0)

Python3

在收藏面经的小蜗牛很想回家

现在数据太强大了，用python根本通过不了，一开始我以为我写的还有可以优化的地方，直到我cv别人的代码发现也通过不了，我就知道这道题的数据又被加强过了。

编辑于 2024-03-27 16:17:21 回复(0)

空照秦淮

#include <stdio.h>
#include<malloc.h>
int main()
{
    int n,*arr;
    scanf("%d",&n);
    arr=(int *)malloc(sizeof(int)*n);
    for(int a=0;a<n;a++)
    {
        scanf("%d",arr+a);
    }
    for(int a=0,e=0,b;a<n;a++)
    {e=0;
        for( b=a-1;b>=0;b--)
        {
            if(*(arr+b)<*(arr+a))
            {
                printf("%d ",b);
                e=1;
                break;
            }
        }
        if(!e)
        {
            printf("-1 ");
        }
        e=0;
        for(b=a+1;b<n;b++)
        {
            if(*(arr+b)<*(arr+a))
            {
                printf("%d",b);
                e=1;
                break; 
            }
        }
        if(!e)
        {
            printf("-1");
        }
    
        printf("\n");
}}

看了评论才知道要用栈，但是，emmm，我这个不用栈为什么也能过啊

发表于 2019-11-11 22:30:44 回复(0)

Java

竹秋

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 * 给定一个可能含有重复值的数组 arr，
 * 找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
 * @author zhuqiu
 * @date 2020/3/25
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = in.nextInt();
        }
        int[] left = new int[len];
        int[] right = new int[len];
        Arrays.fill(right, -1);
        Arrays.fill(left, -1);
        method(len, left, right, arr);
        for (int i = 0; i < len; i++) {
            System.out.printf("%d %d\n", left[i], right[i]);
        }
    }

    public static void method(int len, int[] left, int[] right, int[] arr){
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]){
                right[stack.pop()] = i;
            }
            int top = stack.isEmpty()?-1:stack.peek();
            if (stack.isEmpty()){
            } else if (arr[stack.peek()] != arr[i]){
                left[i] = top;
            } else{
                left[i] = left[top];
            }
            stack.push(i);
        }
    }
}

只有75%，也不知道怎么优化了

发表于 2020-03-25 23:14:28 回复(1)

hid

a=input()
b=[int(i) for i in input().split()]
def left(c):
    n = c - 1
    for j in reversed(b[:c]):
        if b[c]>j:
            return n
        n-=1
    return -1
def right(c):
    n=c+1
    for i in b[c+1:]:
        if b[c]>i:
            return n
        n+=1
    return -1
i=0
while i<len(b):
    cen=b[i]
    if i==0:
        le=-1
        r=right(i)
        print(le,r)
    elif i==len(b)-1:
        le=left(i)
        r=-1
        print(le,r)
    else:
        le=left(i)
        r=right(i)
        print(le,r)
    i+=1

不通过

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

case通过率为25.00%

看看自己25得通过，这个再换c++写一下看能不能通过

发表于 2019-11-05 14:43:34 回复(0)

Javascript

我摸的鱼比你吃的饭还多

贴个 js 版本，需要注意不要逐行输出，不然会一直超时

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    const n = await readline();
    const arr = (await readline()).split(' ').map((item) => Number(item));
    const stack = [];
    const res = new Array(n);

    for (let i = 0; i < n; i++) {
        const cur = arr[i];

        while (stack.length && arr[stack[stack.length - 1]] >= cur) {
            const top = stack.pop();
            res[top] = [stack.length ? stack[stack.length - 1] : -1, i];
        }

        stack.push(i);
    }

    while (stack.length) {
        const top = stack.pop();
        res[top] = [stack.length ? stack[stack.length - 1] : -1, -1];
    }

    for (let i = n - 1; i >= 0; i--) {
        const cur = arr[i];
        let right = res[i][1];

        if (right > 0 && arr[right] === cur) {
            right = res[right][1];
        }

        res[i][1] = right;
    }

    console.log(res.map((item) => item.join(' ')).join('\n'));
}()

发表于 2025-01-18 09:55:33 回复(0)

C++

不爱刷题的芙莉莲

这是一道单调站的模板题目,这是最快的C++的模板,其他语言用这个算法一样

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int stk[N];//手写的栈,常数时间比STL的栈要好
int tt = 0;
int arr[N];
int L[N], R[N]; //左侧第一个比自己小的数字和右侧第一个比自己小的数字

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d",&arr[i]);
    }

    for (int i = 0; i < n; i++) {
        while (tt && arr[i] <= arr[stk[tt]]) {//当栈不空的时候,并且栈顶不是严格单调的时候弹出元素
            R[stk[tt]] = i;
            tt--;
        }
        if (tt)L[i] = stk[tt];//记录左侧答案
        else L[i] = -1;
        stk[++tt] = i;//每一个元素都要进栈
    }
    while (tt) { //清算阶段,因为用
        int t = stk[tt--];
        R[t] = -1;
    }
    for (int i = n-1; i >= 0 ; i--) {//处理相同的情况
        if(arr[R[i]] == arr[i]) R[i] = R[R[i]];
    }
 
    for (int i = 0; i < n; i++) {//输出答案,这里输入输出微末比较大,使用C风格的函数会比CIN,COUT快10倍
        if (L[i] != -1)
            printf("%d ",L[i]);
        else
            printf("-1 ");
        if (R[i] != -1)
            printf("%d \n",R[i]);
        else
            printf("-1 \n");
            
    }

    return 0;
}

发表于 2025-01-08 17:42:47 回复(0)

Java

已注销

// 两次遍历
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.Deque;
import java.util.ArrayDeque;


public class Main {
    private static StreamTokenizer st = new StreamTokenizer(
        new BufferedReader(new InputStreamReader(System.in))
    );

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static int[][] findNearestLessThan(int[] nums) {
        int n = nums.length;
        int[][] res = new int[n][2];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                stack.pop();
            }
            res[i][0] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                stack.pop();
            }
            res[i][1] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        return res;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = nextInt();
        }

        int[][] res = findNearestLessThan(arr);
        StringBuilder sb = new StringBuilder();
        for (int[] pair : res) {
            sb.append(pair[0] + " " + pair[1] + "\n");
        }
        System.out.println(sb);
    }
}

// 一次遍历
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.Deque;
import java.util.ArrayDeque;


public class Main {
    private static StreamTokenizer st = new StreamTokenizer(
        new BufferedReader(new InputStreamReader(System.in))
    );

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static int[][] findNearestLessThan(int[] nums) {
        int n = nums.length;
        int[][] res = new int[n][2];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i <= n; ++i) {
            while (!stack.isEmpty() && (i == n || nums[i] < nums[stack.peek()])) {
                res[stack.pop()][1] = i < n ? i : -1;
            }

            if (i == n) {
                break;
            }

            if (stack.isEmpty()) {
                res[i][0] = -1;
            } else {
                int peek = stack.peek();
                res[i][0] = (nums[i] == nums[peek]) ? res[peek][0] : peek;
            }

            stack.push(i);
        }

        return res;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = nextInt();
        }

        int[][] res = findNearestLessThan(arr);
        StringBuilder sb = new StringBuilder();
        for (int[] pair : res) {
            sb.append(pair[0] + " " + pair[1] + "\n");
        }
        System.out.println(sb);
    }
}

================================================================

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.Deque;
import java.util.ArrayDeque;


public class Main {
    private static StreamTokenizer st = new StreamTokenizer(
        new BufferedReader(new InputStreamReader(System.in))
    );

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static int[][] findNearestLessThan(int[] nums) {
        int n = nums.length;
        int[][] res = new int[n][2];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; ++i) {
            res[i] = new int[] {-1, -1};
        }

        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                res[stack.pop()][1] = i;
            }

            if (!stack.isEmpty()) {
                int peek = stack.peek();
                res[i][0] = (nums[i] == nums[peek]) ? res[peek][0] : peek;
            }
            
            stack.push(i);
        }

        return res;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = nextInt();
        }

        int[][] res = findNearestLessThan(arr);
        StringBuilder sb = new StringBuilder();
        for (int[] pair : res) {
            sb.append(pair[0] + " " + pair[1] + "\n");
        }
        System.out.println(sb);
    }
}

发表于 2024-03-07 10:29:16 回复(0)

C/C++

蝎ie

#include <stdio.h>

#define Max 1000001

int arr[Max];

int ans[Max][2];

int stack[Max];

int n;

// top 指的是栈顶坐标

int top;

void compute(void);

int main() {

while(scanf("%d",&n) != EOF){

// 读入数组

for(int i=0;i<n;i++){

scanf("%d",&arr[i]);

}

// 创建单调栈并获得正确做有下标

compute();

// 输出

for(int i=0;i<n;i++){

printf("%d %d\n",ans[i][0],ans[i][1]);

}

return 0;

}

void compute(void){

// 将栈顶设为0

top = 0;

int cur;

// 遍历数组

for(int i=0;i<n;i++){

// 判断栈是否为空,如果不为空,和栈顶元素比较

while(top > 0 && arr[stack[top - 1]] >= arr[i]){

// 从栈顶弹出元素

cur = stack[--top];

// 记录弹出元素的答案

ans[cur][0] = top == 0 ? -1 : stack[top - 1];

ans[cur][1] = i;

}

// 将i元素压入栈中

stack[top++] = i;

}

// 清空阶段(清理栈)

while(top > 0){

// 将栈顶元素弹出,并记录答案

cur = stack[--top];

ans[cur][0] = top == 0 ? -1 : stack[top - 1];

ans[cur][1] = -1;

}

// 修改阶段

// 从后往前遍历,修改右下表数组错误答案

for(int i=n-2;i>=0;i--){

if(ans[i][1] != -1 && arr[i] == arr[ans[i][1]]){

ans[i][1] = ans[ans[i][1]][1];

}

编辑于 2024-01-22 13:29:57 回复(0)

Python

AndrewJohn

# 用list模拟单调栈
n = int(input())
arr = [int(k) for k in input().split()]
left = [-1 for _ in range(n)]
stk = []
# 左向右
for i in range(n):
    while stk and arr[stk[-1]] >= arr[i]:
        stk.pop()
    if stk:
        left[i] = stk[-1]
    stk.append(i)
right = [-1 for _ in range(n)]
stk = []
# 右向左
for i in range(n-1, -1, -1):
    while stk and arr[stk[-1]] >= arr[i]:
        stk.pop()
    if stk:
        right[i] = stk[-1]
    stk.append(i)
for i in range(n):
    print(f"{left[i]} {right[i]}")

编辑于 2022-07-19 07:55:49 回复(1)

Java

牛客840012699号

public /*List<Integer[]>*/static void test(int[] arr) {
        int n = arr.length;
        int[] left = new int[n];
        left[0] = 0;
        for (int i = 1; i < n; i++) {
            if (arr[left[i - 1]] > arr[i])
                left[i] = i;
            else left[i] = left[i - 1];
        }

        int[] right = new int[n];
        right[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[right[i + 1]] > arr[i])
                right[i] = i;
            else right[i] = right[i + 1];
        }

        StringBuilder sb = new StringBuilder();

        int l = -1, r = 0;
        if (arr[right[1]] < arr[0]) {
            while (++r < n && arr[r] >= arr[0]) ;
        } else
            r = -1;
        sb.append("-1 ").append(r).append("\n");
//        System.out.println("-1 " + r);

        for (int i = 1; i < n - 1; i++) {
            if (arr[i] > arr[left[i - 1]]) {   // 左边存在较小的值
                if (arr[i - 1] < arr[i])
                    l = i - 1;
                else if (arr[i - 1] > arr[i]) {
                    l = i;
                    while (--l >= 0 && arr[l] >= arr[i]) ;
                }
            } else l = -1;

            if (arr[i] > arr[right[i + 1]]) {  // 右边存在较小的值
                r = i;
                while (++r < n && arr[r] >= arr[i]) ;
            } else r = -1;
//            System.out.println(l + " " + r);
            sb.append(l).append(" ").append(r).append("\n");

//            res.add(new Integer[]{l, r});
        }
        l = n - 1;
        if (arr[left[n-2]] < arr[n - 1]) {
            while (--l < n && arr[l] >= arr[n - 1]) ;
        } else
            l = -1;
        sb.append(l).append(" -1\n");
        System.out.println(sb);
    }

public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = Integer.parseInt(s.nextLine().trim());
        int[] arr = new int[n];
        String[] strings = s.nextLine().trim().split(" ");
        for (int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(strings[i]);
        }
        Main.tets(arr);

    }

中心拓展

发表于 2021-12-08 23:03:02 回复(0)

Java

H.T.W

Java输入输出都用Buffer可以不超时。

import java.io.*;
import java.util.Arrays;
import java.util.Stack;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(reader.readLine());

        int[] arr = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int[] left = new int[n];
        int[] right = new int[n];

        /**
         * 单调递增栈
         */
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                right[stack.pop()] = i;
            }
            left[i] = stack.isEmpty() ? -1 : (arr[stack.peek()] == arr[i] ? left[stack.peek()] : stack.peek());
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            right[stack.pop()] = -1;
        }

        for (int i = 0; i < n; ++i) {
            writer.write(left[i] + " " + right[i]);
            writer.newLine();
        }
        writer.flush();
    }
}

发表于 2021-08-27 14:21:59 回复(0)

C++

牛客890394445号

这题咋这么离谱呢，使用cout cin就超时，非要用scanf，与printf？改了半天代码对比评论区才发现是这问题。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
	int size;
    scanf("%d", &size);
	vector<int> arr(size);
    vector<int> ans1(size,-1);
    vector<int> ans2(size,-1);
	stack<int> s;
	stack<int> s1;
	for (int i = 0; i < size; i++)
    {
        scanf("%d", &arr[i]);
        while (!s.empty() && arr[s.top()] >= arr[i])
		{
			s.pop();
		}
		if (!s.empty()) ans1[i] = s.top();
		s.push(i);
    }
	for (int i = size - 1; i >= 0; i--)
	{
		while (!s1.empty() && arr[s1.top()] >= arr[i])
		{
			s1.pop();
		}
		if (!s1.empty()) ans2[i] = s1.top();
		s1.push(i);

	}
	
    for (int i = 0 ; i < size; i++)
    {
        printf("%d %d\n", ans1[i], ans2[i]);
    }
	return 0;
}

发表于 2021-08-25 20:40:29 回复(0)

单调栈结构(进阶)

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题