下一个较大元素_

推荐

念润

思路：

从后向前维护一个递减栈。

最右边的那个值肯定没有最大值，所以肯定是-1。初始栈为-1。

从后向前计算：

（1）如果当前元素大于栈顶元素，则栈顶元素退出，如果还是大于栈顶元素，继续退出，一直遍历栈到-1或者小于栈顶元素。这个元素就是就是当前值的下一个比较大的元素。

（2）如果当前元素小于栈顶元素，栈顶元素就是当前值的下一个比较大的元素。

再简化一下代码如下

代码：

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;
    }
};

编辑于 2015-08-16 17:03:26 回复(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)

luohan

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)

Java

pein531

单调栈

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)

Java

lmz9509

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)

C/C++

十二只猴子

我写下暴力遍历方法，虽然没有用到栈，且不符合题意，但是测试用例都能通过。
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]

发表于 2019-06-13 11:14:40 回复(0)

ID84848484

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;
    }
}

发表于 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)

C/C++

Cavs

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)

_XiaoTeng_

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)

Aurora1

class NextElement:
    def findNext(self, A, n):
        s, b = [-1], []
        for i in xrange(1, n + 1):
            while len(s) > 0 and A[-i] > s[-1]:
                s.pop()
            t = -1 if len(s) == 0 else s[-1]
            b.insert(0, t)
            s.append(A[-i])
        return b

发表于 2017-03-17 21:40:46 回复(0)

Ron

    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)

牛客297184号

基本思路:遍历数组,把栈中比当前数组的数小的数全部出栈并将其后续元素标记为当前数组元素.然后把当前数组元素进栈.遍历完成后,栈中仍然存在的元素设置为-1.

发表于 2015-09-30 09:47:30 回复(0)

C++

天不生我李淳罡，剑道万古如长夜

只要将满足前一个数比自己大的数存入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)

C/C++

codewind

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:
    def findNext(self, A, n):
        res = []
        for i in range(n-1):
            re = []
            for j in range(i+1,n):
                if A[j] > A[i]:
                    re.append(A[j])
                    res.append(A[j])
                    break
            if re == []:
                res.append(-1)
        res.append(-1)
        return res

发表于 2020-08-11 19:32:42 回复(0)

TankWitch

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)

snail_lx

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)

下一个较大元素

问题信息

热门推荐

通过挑战的用户

相关试题