给定一个int数组A及其大小n,返回一个int数组,int数组中的元素是原数组中每个元素比他大的下一个元素,若不存在则为-1。保证数组中元素均为正整数。
测试样例:
[11,13,10,5,12,21,3],7
返回:[13,21,12,12,21,-1,-1]
import java.util.*; public class NextElement { public int[] findNext(int[] arr, int n) { // write code here Stack<Integer> stack = new Stack<>(); int[] res = new int[n]; for(int i = 0; i < n; i++){ if(stack.isEmpty()){ stack.push(i); }else{ if(arr[stack.peek()] > arr[i]){ stack.push(i); }else{ while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) res[stack.pop()] = arr[i]; stack.push(i); } } } while(!stack.isEmpty()) res[stack.pop()] = -1; return res; } }
import java.util.*; /* 双重for循环 */ public class NextElement { public int[] findNext(int[] A, int n) { // write code here int[] result = new int[n]; for(int i = 0;i<n;i++){ int temp = A[i]; int j = i + 1; for(;j<n;j++){ if(A[j] > temp){ result[i]=A[j]; break; } } if(j==n) result[i] = -1; } return result; } }
import java.util.*; public class NextElement { public int[] findNext(int[] A, int n) { if(n<1) return null; int[] res=new int[n]; for(int i=0;i<n;i++){ res[i]=-1; } Stack<Integer> s=new Stack<Integer>(); for(int i=0;i<n;i++){ while(!s.isEmpty()&&A[i]>A[s.peek()]) res[s.pop()]=A[i]; s.push(i); } return res; } }