给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
[编程题]单调栈结构(进阶)
#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)
注意避免输出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)
栽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)
头条一面没写出来，现在运行不出来
#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)
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)
#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;
#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 <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)
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)
#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)
#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)
现在数据太强大了，用python根本通过不了，一开始我以为我写的还有可以优化的地方，直到我cv别人的代码发现也通过不了，我就知道这道题的数据又被加强过了。
编辑于 2024-03-27 16:17:21
回复(0)
// 两次遍历
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)
#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)
# 用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)
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输入输出都用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)
这题咋这么离谱呢，使用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)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
int[] arr = new int[N];
String[] s = reader.readLine().split(" ");
reader.close();
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(s[i]);
}
int[][] res = new int[arr.length][2];
Stack<List<Integer>> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
List<Integer> popIndexs = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popIndex : popIndexs) {
res[popIndex][0] = leftLessIndex;
res[popIndex][1] = i;
}
}
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(i);
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
while (!stack.isEmpty()) {
List<Integer> popIndexs = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popIndex : popIndexs) {
res[popIndex][0] = leftLessIndex;
res[popIndex][1] = -1;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.length; i++) {
sb.append(res[i][0] + " " + res[i][1] + "\n");
}
System.out.println(sb.toString());
}
}
一定要注意IO
发表于 2021-08-06 11:50:44
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] nums = new int[num];
for(int i = 0 ; i < num ; i++ ){
nums[i] = sc.nextInt();
}
int[][] res = solution(nums);
for(int i = 0 ; i < res.length; i ++ ){
for(int j = 0 ; j < res[0].length ; j++ ){
System.out.print(res[i][j]);
System.out.print(" ");
}
System.out.println();
}
}
public static int[][] solution(int[] heights) {
int len = heights.length;
int[][] res = new int[len][2];
Stack<Integer> mono_stack = new Stack<Integer>();
for (int i = 0; i < len; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
int index = mono_stack.pop();
int indexLess = mono_stack.isEmpty()?-1:mono_stack.peek();
res[index][0] = indexLess;
res[index][1] = i;
}
mono_stack.push(i);
}
while(!mono_stack.isEmpty()){
int index = mono_stack.pop();
int indexLess = mono_stack.isEmpty()?-1:mono_stack.peek();
res[index][0] = indexLess;
res[index][1] = -1;
}
return res;
}
3
/// 为啥一直内存不够啊
}
发表于 2021-07-30 20:33:47
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-11 21:10:47
-
2022-10-13 14:36:21
-
2022-09-12 23:01:03
-
2022-09-11 20:24:12 -
2022-09-07 11:46:42
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
