给定一个int数组A及其大小n，返回一个int数组，int数组中的元素是原数组中每个元素比他大的下一个元素,若不存在则为-1。保证数组中元素均为正整数。
测试样例：
[11,13,10,5,12,21,3],7
返回：[13,21,12,12,21,-1,-1]
[编程题]下一个较大元素
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
vector<int>res(n);
stack<int>st;
for(int i=0;i<n;){
if(st.empty()||A[st.top()]>=A[i]){
st.push(i);
i++;
}
else{
res[st.top()]=A[i];
st.pop();
}
}
while(!st.empty()){
res[st.top()]=-1;
st.pop();
}
return res;
}
};
发表于 2019-09-07 15:57:24
回复(0)
更多回答
import java.util.*;
public class NextElement {
public int[] findNext(int[] A, int n) {
// write code here
Stack<Integer> stack=new Stack<Integer>();
for(int i=0;i<A.length;i++){
while(!stack.isEmpty()&&A[stack.peek()]<A[i]){
A[stack.pop()]=A[i];
}
stack.add(i);
}
while(!stack.empty())
A[stack.pop()]=-1;
return A;
}
}
发表于 2017-05-30 17:14:43
回复(1)
O(N)算法
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
stack<int> ss;
vector<int> result;
for (int i = n - 1; i >= 0; -- i) {
// 每个元素实际上只入栈一次，出栈一次，所以是O(N)的
while (!ss.empty() && A[i] >= ss.top())
ss.pop();
if (ss.empty()) {
result.push_back(-1);
} else {
result.push_back(ss.top());
}
ss.push(A[i]);
}
reverse(result.begin(), result.end());
return result;
}
};
发表于 2016-08-28 01:54:19
回复(1)
import java.util.*;
/*
思路：讲道理这题目我觉得直接遍历不会很慢，我就想到了这种方法,
事实上我这方法耗时太高了。再试试用栈的方法——耗时更高了- -这算神马
*/
/*
public class NextElement {
public int[] findNext(int[] A, int n) {
int b[] =new int[n];
for(int i=0;i<n;i++){
int j=i+1;
while(j<n&&A[i]>A[j]){
j++;
}
if(j!=n) b[i]=A[j];
else b[i]=-1;
}
return b;
}
}
运行时间：572ms
占用内存：18156k
*/
public class NextElement {
public int[] findNext(int[] A, int n) {
if(A==null||A.length==0) return null;
Stack<Integer> stack =new Stack<>();
int b[] =new int[n];
for(int end =n-1;end>=0;end--){
//栈顶的元素值都没有接下来的元素大，那就把出栈，继续比较，直到栈空或者找到比A[end]大的值
while(!stack.isEmpty()&&A[end]>=stack.peek()){
stack.pop();
}
if(stack.isEmpty()){
stack.push(A[end]);
b[end]=-1;
continue;
}
if(A[end]<stack.peek()){
b[end]=stack.peek();
stack.push(A[end]);
}
}
return b;
}
}
运行时间：760ms
占用内存：18116k
发表于 2017-07-06 16:47:46
回复(0)
单调栈
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;
}
}
发表于 2021-11-25 22:24:43
回复(0)
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;
}
}
发表于 2020-06-06 14:46:38
回复(0)
我写下暴力遍历方法，虽然没有用到栈，且不符合题意，但是测试用例都能通过。
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
// write code here
vector<int> ans;
for(int i=0;i<n;i++)
{
for (int j=i+1;j<n;j++)
{
if (A[j]>A[i])
{
ans.push_back(A[j]);
break;
}
if (j==n-1 && A[j]<=A[i])
ans.push_back(-1);
}
}
ans.push_back(-1);
return ans;
}
};
发表于 2019-07-22 21:57:14
回复(0)
class NextElement:
def findNext(self, A, n):
# write code here
stack=[]
res=[]
for i in range(n-1,-1,-1):
while stack!=[] and A[i]>=stack[-1]:
stack.pop()
if stack==[]:
res.append(-1)
stack.append(A[i])
else:
res.append(stack[-1])
stack.append(A[i])
return res[::-1]
def findNext(self, A, n):
# write code here
stack=[]
res=[]
for i in range(n-1,-1,-1):
while stack!=[] and A[i]>=stack[-1]:
stack.pop()
if stack==[]:
res.append(-1)
stack.append(A[i])
else:
res.append(stack[-1])
stack.append(A[i])
return res[::-1]
发表于 2019-06-13 11:14:40
回复(0)
import java.util.*;
public class NextElement {
public int[] findNext(int[] A, int n) {
// write code here
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=-1;
for(int j=i+1;j<n;j++){
if(A[j]>A[i])
{
arr[i]=A[j];
break;
}
}
}
return arr;
}
}
public int[] findNext(int[] A, int n) {
// write code here
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=-1;
for(int j=i+1;j<n;j++){
if(A[j]>A[i])
{
arr[i]=A[j];
break;
}
}
}
return arr;
}
}
发表于 2019-05-27 00:05:48
回复(0)
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
//简单思路：逐个比较即可
//定义结果数组
vector<int> result;
//比较，赋值
for (int i = 0; i < n; i++) {
if (i == n - 1) {
result.push_back(-1);
break;
}
for (int j = i+1; j < n; j++) {
if (A.at(i) < A.at(j)) {
result.push_back(A.at(j));
break;
}
if (j == n - 1) {
result.push_back(-1);
}
}
}
return result;
}
};
运行时间：7ms；
内存占用：574k；
与用栈的方式比较发现，这种暴力比较的方式的运行效率比用栈的方式高~~~~
发表于 2017-11-24 23:36:36
回复(1)
class NextElement {
public:
vector<int> findNext(vector<int> A, int n)
{
vector<int> res(n);
res[n-1] = -1;
stack<int> stk;
stk.push(A[n - 1]);
for(int i = n - 2;i >= 0;--i)
{
while(!stk.empty() && stk.top() <= A[i]) stk.pop();
res[i] = stk.empty() ? -1:stk.top();
stk.push(A[i]);
}
return res;
}
};
发表于 2017-06-30 21:39:45
回复(0)
public int[] findNext(int[] A, int n) {
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i = n - 1; i >= 0; i--){
while(!stack.isEmpty() && stack.peek() <= A[i]){
stack.pop();
}
res[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(A[i]);
}
return res;
}
发表于 2017-05-02 17:04:02
回复(1)
public int[] findNext(int[] A, int n) {
// write code here
if(A == null){
return new int[]{};
}
Stack<Integer> list = new Stack<Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
for(int i = n-1; i >= 0; i--){
if(i == n-1){
res.add(-1);
list.push(A[i]);
}else{
while(!list.empty() && list.peek() <= A[i]){
list.pop();
}
if(list.empty()){
res.add(-1);
}else{
res.add(list.peek());
}
list.push(A[i]);
}
}
System.out.println(res);
int[] mat = new int[n];
for(int i = 0; i < n; i++){
mat[i] = res.get(n-1-i);
}
return mat;
}
发表于 2016-06-22 17:56:18
回复(1)
classNextElement {
public:
vector<int> findNext(vector<int> A, intn) {
vector<int> res;
if(n == 0)
returnres;
res = A;
stack<int> s;
s.push(A[n-1]);
res[n-1] = -1;
for(inti=n-2;i>=0;i--)
{
while(!s.empty() && A[i]>=s.top())
{
s.pop();
}
if(s.empty())
res[i] = -1;
else
res[i] = s.top();
s.push(A[i]);
}
returnres;
}
};
从后往前维护一个递减栈就行了
发表于 2015-07-28 19:12:48
回复(0)
只要将满足前一个数比自己大的数存入help，并在help中查找第一个大于A[i]的数，就能得到结果
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
// write code here
vector<int> res;
vector<int> help;
int max=-1;
for(int i=n-1;i>=0;i--){
//前面一个比当前值大就放入help中
if(i!=0&&A[i]>A[i-1]){
help.push_back(A[i]);
//help中的最大值max
if(A[i]>max)
max=A[i];
}
//如果当前值大于等于help中的最大值，则help中没有值大于当前值
if(A[i]>=max)
res.insert(res.begin(), -1);
else
//找help中第一个大于A[i]的数
for(int j=help.size()-1;j>=0;j--)
if(help[j]>A[i]){
res.insert(res.begin(), help[j]);
break;
}
}
return res;
}
};
发表于 2022-02-15 13:51:48
回复(0)
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
// write code here
if(n<=1) return {-1};
vector<int> res;
for(int i=0;i<n;++i) {
bool fill = false;
for(int j=i+1;j<n;++j) {
if(A[j]> A[i]) {
res.push_back(A[j]);
fill = true;
break;
}
}
if(fill) continue;
res.push_back(-1);
}
return res;
}
}; 直接暴力法
发表于 2021-01-30 16:25:11
回复(0)
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
// write code here
vector<int> ret;
stack<int> stk;
stk.push(-1);
for (int i = n-1; i >= 0; --i) {
while (!stk.empty() && A[i] >= stk.top()) {
stk.pop();
}
if (stk.empty()) {
ret.push_back(-1);
} else {
ret.push_back(stk.top());
}
stk.push(A[i]);
}
reverse(ret.begin(), ret.end());
return ret;
}
};
发表于 2020-08-01 09:02:55
回复(0)
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
vector<int> B(n);
bool flag=false;
for(int i=0;i<n;i++){
for(int j=i+1;(j<n)&&(!flag);j++){
if(A[j]>A[i]){
B[i]=A[j];
flag=true;
}
}
if(!flag){
B[i]=-1;
}
flag=false;
}
return B;// write code here
}
};
//8ms 596KB
发表于 2020-07-31 21:18:42
回复(0)
问题信息
难度：
65条回答
71收藏
13863浏览
通过挑战的用户
查看代码-
2022-11-01 23:07:48 -
2022-09-11 11:04:23 -
2022-08-29 21:13:53
-
2022-08-26 11:26:50 -
2022-08-25 21:32:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class NextElement { public: vector<int> findNext(vector<int> A, int n) { vector<int> result; if(n <= 0){ return result; }//if stack<int> stack; stack.push(-1); for(int i = n-1;i >= 0;--i){ int top = stack.top(); while(top != -1 && A[i] >= top){ stack.pop(); top = stack.top(); }//while result.insert(result.begin(),top); stack.push(A[i]); }//for return result; } };