给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
[编程题]单调栈结构(进阶)
// 两次遍历
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)
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)
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)
Java,思路：利用之前的left和right数组信息，通过100%。
import java.io.*;
import java.util.*;
public class Main {
public static int n;
public static int[] arr;
public static BufferedReader buf;
public static int[] left;
public static int[] right;
public static void process() {
//第一个数的左边不存在比它小的
left[0] = -1;
right[arr.length - 1] = -1;
//求左边比它小的
for (int i = 1; i < arr.length; i++) {
int temp = i - 1;
//利用之前的left数组信息
while (temp >= 0 && arr[temp] >= arr[i]) {
temp = left[temp];
}
left[i] = temp;
}
//求右边比它小的
for (int i = arr.length - 2; i >= 0; i--) {
int temp = i + 1;
while (temp >= 0 && arr[temp] >= arr[i]) {
temp = right[temp];
}
right[i] = temp;
}
}
public static void main(String[] args) throws IOException {
buf = new BufferedReader(new InputStreamReader(System.in));
String[] strs;
n = Integer.parseInt(buf.readLine());
arr = new int[n];
left = new int[n];
right = new int[n];
strs = buf.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(strs[i]);
}
process();
for (int i = 0; i < n; i++) {
System.out.println(left[i] + " " + right[i]);
}
}
}
编辑于 2021-04-10 01:07:25
回复(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)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
public class Main {
public static int[][] getNear(int a[])
{
int value[][] = new int[a.length][2];
Stack<ArrayList<Integer>> stack = new Stack<>();
int index = 0;
for (int i = 0; i < a.length; i++) {
while(!stack.isEmpty()&&a[i]<a[stack.peek().get(0)])
{
ArrayList<Integer> pop = stack.pop();
for (Integer p : pop) {
value[p][1] = i;
value[p][0] = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
}
}
if(!stack.isEmpty() && a[i] == a[stack.peek().get(0)])
{
stack.peek().add(i);
}else{
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
while(!stack.isEmpty())
{
ArrayList<Integer> pop = stack.pop();
for (Integer p : pop) {
value[p][1] = -1;
value[p][0] = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
}
}
return value;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int a[] = new int[n];
String[] s = reader.readLine().split(" ");
for (int i = 0; i < a.length; i++) {
a[i] = Integer.parseInt(s[i]);
}
int[][] near = getNear(a);
for (int i = 0; i < near.length; i++) {
System.out.println(near[i][0]+" "+near[i][1]);
}
}
}
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
public class Main {
public static int[][] getNear(int a[])
{
int value[][] = new int[a.length][2];
Stack<ArrayList<Integer>> stack = new Stack<>();
int index = 0;
for (int i = 0; i < a.length; i++) {
while(!stack.isEmpty()&&a[i]<a[stack.peek().get(0)])
{
ArrayList<Integer> pop = stack.pop();
for (Integer p : pop) {
value[p][1] = i;
value[p][0] = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
}
}
if(!stack.isEmpty() && a[i] == a[stack.peek().get(0)])
{
stack.peek().add(i);
}else{
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
while(!stack.isEmpty())
{
ArrayList<Integer> pop = stack.pop();
for (Integer p : pop) {
value[p][1] = -1;
value[p][0] = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
}
}
return value;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int a[] = new int[n];
String[] s = reader.readLine().split(" ");
for (int i = 0; i < a.length; i++) {
a[i] = Integer.parseInt(s[i]);
}
int[][] near = getNear(a);
for (int i = 0; i < near.length; i++) {
System.out.println(near[i][0]+" "+near[i][1]);
}
}
}
发表于 2021-02-22 21:50:26
回复(1)
import java.util.Arrays;
import java.util.Scanner;
/**
* @ Created with IntelliJ IDEA.
* @ClassName Test1
* @Description 输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始
* @Author by小房
* @Date 2020/7/25 12:51
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] array = new int[N];
for (int i = 0; i < N; i++) {
array[i] = scanner.nextInt();
}
for (int i = 0; i < N ; i++) {
toFind(array, array[i], i);
}
}
private static void toFind(int[] array, int num, int i) {
int left = -1;
int right = -1;
for (int j = i; j >= 0 ; j--) {
if (array[j] < num) {
left = j;
break;
}
}
for (int j = i+1; j < array.length ; j++) {
if (array[j] < num) {
right = j;
break;
}
}
System.out.println(left + " " + right);
}
}
发表于 2020-07-25 14:06:38
回复(1)
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)
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];
for(int i=0;i<n;i++)
{
arr[i] = sc.nextInt();
}
int l,r;
StringBuffer sb = new StringBuffer();
for(int i=0;i<n;i++)
{
l = -1;
r = -1;
for(int j = i-1;j>-1;j--)
{
if(arr[j]<arr[i])
{
l = j;
break;
}
}
for(int j = i+1;j<n;j++)
{
if(arr[j]<arr[i])
{
r = j;
break;
}
}
sb.append(l+" "+r+"\n");
}
System.out.print(sb.toString());
}
}
发表于 2019-08-28 13:29:04
回复(1)
问题信息
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
