下一个较大元素II_

阿狸不是猫

import java.util.*;
/*
思路：这题目比上一道题目要复杂一点，需要用到辅助栈，这是因为所求的是比它大的最小的元素
因此需要保证栈内元素的有序性，这样依次比较才合理
*/
public class NextElement {
    public int[] findNext(int[] A, int n) {
        if(A==null||A.length==0) return null;
        Stack<Integer> stack1 =new Stack<>();//将stack1作为主栈
        Stack<Integer> stack2 =new Stack<>();//将stack2作为辅助栈
        int b[] =new int[n];
        for(int end =n-1;end>=0;end--){
            //最麻烦的一环，如果大于栈顶的元素，那就应该将栈顶的元素放入辅助栈中
            //继续比较，直到小于栈顶元素或者主栈为空
            //这个应该放在第一个作判断
            while(!stack1.isEmpty()&&A[end]>=stack1.peek()){
                stack2.push(stack1.pop());
            }
			//如果小于栈顶的元素，即小于栈中最小元素
            //栈为空这个判断放到最后比较合理
            //还要记得把辅助栈内的数据导回到主栈中
            if(stack1.isEmpty()){
                stack1.push(A[end]);
                b[end]=-1;
            }else{
                b[end] =stack1.peek();
                stack1.push(A[end]);
            }
             while(!stack2.isEmpty()){
                    stack1.push(stack2.pop());
                }
        }
        return b; 
    }
}

发表于 2017-07-09 12:06:47 回复(1)

revivedSuN

class NextElement {
public:

    vector<int> findNext(vector<int> A, int n) {
        // write code here
        set<int> st;
        set<int>::iterator it;
        st.insert(-1);
        for(int i = n - 1; i >= 0; i--){
            it = upper_bound(st.begin(),st.end(),A[i]);
            if(it != st.end()){
                int tmp = A[i];
                A[i] = *it;
                st.insert(tmp);
            }else{
                st.insert(A[i]);
                A[i] = -1;
            }
        }
        return A;
    }
};

发表于 2015-08-19 11:58:55 回复(0)

L0L

class NextElement {
public:
    vector<int> findNext(vector<int> A, int n) {
        vector<int> dp(n,-1);
        int i,j;
        for(i=n-2;i>=0;--i){
            for(j=i+1;j<n;j++){
                if(A[i]<A[j]){
                    if(dp[i] == -1){
                        dp[i] = A[j];
                    }else{
                        dp[i] = min(dp[i],A[j]);
                    }
                }
            }
        }
        return dp;
    }
};

发表于 2015-10-19 18:11:55 回复(0)

_XiaoTeng_

 public int[] findNext(int[] A, int n) {
       int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        for(int i = n - 1; i >= 0; i--){
            while(!stack.isEmpty() && stack.peek() <= A[i]){
                stack2.push(stack.pop());
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(A[i]);
            while(!stack2.isEmpty()){
                stack.push(stack2.pop());
            }
        }
        return res;
    }

发表于 2017-05-02 17:18:23 回复(2)

Java

pein531

这个题真搞笑，用暴力法竟然能过

import java.util.*;

public class NextElement {
    public int[] findNext(int[] arr, int n) {
        // write code here
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for(int i = 0; i < n - 1; i++){
            for(int j = i + 1; j < n; j++)
                if(arr[j] > arr[i]) res[i] = res[i] != -1? Math.min(res[i], arr[j]): arr[j];
        }
        return res;
    }
}

发表于 2021-11-25 22:31:57 回复(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 min = Integer.MAX_VALUE;
            for(int j = i +1;j<n;j++){
                if(A[j] > A[i]){
                    min = Math.min(min,A[j]);
                }
            }
            if(min==Integer.MAX_VALUE)
                result[i] = -1;
            else
                result[i] = min;
        }
        return result;
    }
}

发表于 2020-06-06 15:02:38 回复(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++){
            int tem=Integer.MAX_VALUE;
            for(int j=i+1;j<n;j++){
                if(A[j]>A[i]){
                    if(tem>A[j])
                        tem=A[j];
                }
            }
            if(tem==Integer.MAX_VALUE)
                arr[i]=-1;
            else
                arr[i]=tem;
        }
        return arr;
    }
}

发表于 2019-05-27 15:15:59 回复(0)

jiangcw

//第一感觉的想法，各位有啥好方法，求告知

import java.util.*;

public class NextElement {
    public int[] findNext(int[] A, int n) {
        // write code here
        if(n <= 0)
            return null;
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        int[] result = new int[n];
        for(int i = n -1; i >= 0; i--){
            while(!stack1.empty() && stack1.peek() <= A[i]) {
                stack2.push(stack1.pop());
            }
            result[i] = stack1.empty()? -1 : stack1.peek();
            stack1.push(A[i]);
            while(!stack2.empty()){
                stack1.push(stack2.pop());
            }
        }
        return result;
    }
}

编辑于 2017-06-10 20:23:00 回复(4)

铭曦

利用一个辅助栈维护一个有序栈 
class NextElement {
	vector<int> result;//存放结果
public:
	vector<int> findNext(vector<int> A, int n) 
	{
		// write code here
		result.push_back(-1);
		stack<int> s1,s2;//s2是辅助用处的栈
		s1.push(A.at(n - 1));
		for (int i = n - 2; i >= 0; --i) 
		{
			while (!s1.empty()) 
			{ 
				if (A.at(i) > s1.top())
				{
					s2.push(s1.top());
					s1.pop();
				}
				else
					break;
			}
			if (!s1.empty()) 
				result.push_back(s1.top());
			else 
				result.push_back(-1);
			s1.push(A.at(i));
			//维护s1的已序
			while (!s2.empty()) 
			{
				s1.push(s2.top());
				s2.pop();
			}
		}
		reverse(result.begin(),result.end());
		return result;
	}
};

发表于 2017-05-06 17:09:22 回复(0)

Java

Holiday_12138

import java.util.*;

public class NextElement {
    public int[] findNext(int[] A, int n) {
        if(n<1)
            return null;
        TreeSet<Integer> ts=new TreeSet<Integer>();
        int[] res=new int[n];
        for(int i=n-1;i>=0;i--){
            ts.add(A[i]);
            if(ts.higher(A[i])!=null)
                res[i]=ts.higher(A[i]);
            else
                res[i]=-1;
        }
        return res;
    }
}

发表于 2017-05-04 14:54:16 回复(1)

Aurora1

class NextElement:
    def findNext(self, A, n): #选择排序思想
        k = [-1] * n
        for i in xrange(n):
            t = A[i]
            for j in xrange(i + 1, n):
                if A[j] > A[i]:
                    if t == A[i] or t > A[j]:
                        t = A[j]
            k[i] = -1 if t == A[i] else t
        return k

编辑于 2017-03-18 21:13:33 回复(0)

幻之飞雪

public static int[] findNext(int[] A, int n) {
        // write code here
        Stack<Integer> temp=new Stack<Integer>();
        temp.push(-1);
        ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=n-1;i>=0;--i){
         int len=temp.size();
         int top=0;
         int j;
         for(j=len-1;j>0;--j){
         top=temp.get(j);
         if(top>A[i]){
         temp.add(j+1,A[i]);
         list.add(top);
         break;
         }
         }
         if(j==0){
         temp.add(1, A[i]);
         list.add(-1);
         }
        }
        int[] B=A;
        for(int i=n-1;i>=0;--i)
         B[i]=list.get(n-i-1);
        
        return B;
}

用可插入栈实现。

发表于 2016-06-12 20:56:14 回复(0)

zyweng

//从后往前开始遍历
class NextElement {
public:
    vector<int> findNext(vector<int> A, int n) {
        // write code here
        vector<int> dp(n,-1);
        int i,j;
        for(i=n-2;i>=0;--i){
            for(j=i+1;j<n;j++){
                if(A[i]<A[j]){
                    if(dp[i] == -1){
                        dp[i] = A[j];
                    }else{
                        dp[i] = dp[i]<A[j]?dp[i]:A[j];
                    }
                }
            }
        }
        return dp;
    }
};

发表于 2015-09-07 15:18:47 回复(0)

念润

思路

从后向前遍历，对于每一个元素，再从其后一个元素开始寻找比它大的最小元素，我是map来存储其后面元素的，所以只要遍历map，如果到达map末尾之前找到的第一个比它大的元素即是我们找的目标；如果到达map末尾还是没找到则是-1

或者不用遍历而是用map的库函数upper_bound(A[i])寻找比A[i]大的最小元素。

代码

class NextElement {
public:
    vector<int> findNext(vector<int> A, int n) {
        vector<int> result;
        int size = A.size();
        if(size == 0 || n <= 0){
            return result;
        }//if
        map<int,int> Map;
        for(int i = size - 1;i >= 0;--i){
            map<int,int>::iterator ite = Map.begin();
            // 每个元素的后面比它大的最小的元素
            while(ite != Map.end() && A[i] >= ite->first){
                ++ite;
            }//while
            // 未找到
            if(ite == Map.end()){
                result.insert(result.begin(),-1);
            }//if
            else{
                result.insert(result.begin(),ite->first);
            }//else
            Map.insert(make_pair(A[i],i));
        }//for
        return result;
    }
};

编辑于 2015-08-18 21:07:09 回复(1)

luohan

使用set, O(NlogN)

class NextElement {
public:
    vector<int> findNext(vector<int> A, int n) {
        set<int> ss;
        vector<int> result;
        for (int i = n - 1; i >= 0; -- i) {
            auto pos = ss.lower_bound(A[i]);
            if (pos != ss.end() && *pos == A[i])
                ++ pos;
            
            if (pos == ss.end()) {
                result.push_back(-1);
            } else {
                result.push_back(*pos);
            }
            ss.insert(A[i]);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

发表于 2016-08-28 03:34:13 回复(3)

向同于桌

class NextElement {
public:
    vector<int> findNext(vector<int> A, int n) {
        // write code here
        vector<int>result(n,-1);
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;j++)
            {
            if(A[j]>A[i]){
            if(result[i]==-1)
                {
                result[i]=A[j];
            }else
                result[i]=min(A[j],result[i]);
            }
        }
        return result;
    }
};

发表于 2015-08-25 23:42:27 回复(1)

奥利给任一一

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])
            if re == []:
                res.append(-1)
            else:
                res.append(min(re))
        res.append(-1)
        return res

发表于 2020-08-11 19:38:28 回复(0)

TankWitch

class NextElement {
public:
    vector<int> findNext(vector<int> A, int n) {
        // write code here
        vector<int> ret;
        set<int> s;
        for (int i = n-1; i >= 0; --i) {
            auto itr = s.upper_bound(A[i]);
            if (itr == s.end() ) {
                ret.push_back(-1);
            } else {
                ret.push_back(*itr);
            }
            s.insert(A[i]);
        }
        reverse(ret.begin(), ret.end() );
        return ret;
    }
};

发表于 2020-08-01 11:22:51 回复(0)

包子冲汤胡辣汤

class NextElement {
public:
    const int inf=999999999;
    vector<int> findNext(vector<int> a, int n) {
        // write code here
        vector<int> v;
        for(int i=0;i<n-1;++i){
            int mmax=inf;
            for(int j=i+1;j<n;++j){
                if(a[i]<a[j]&&a[j]<mmax){
                    mmax=a[j];
                }
            }
            if(mmax==inf)
                v.push_back(-1);
            else
                v.push_back(mmax);
        }
        v.push_back(-1);
        return v;
    }
};

发表于 2020-04-03 23:37:08 回复(0)

Nick_liu

public class NextElement {
    public class TreeNode{
        int val ;
        TreeNode left ;
        TreeNode right ;

        public TreeNode (int x ) {
            this.val = x ;
        }

        public void build(int x){
            if ( x<this.val ){
                if(this.left!=null){
                    this.left.build(x);
                } else {
                    this.left = new TreeNode(x);
                }
            } else {
                if(this.right!=null){
                    this.right.build(x);
                } else {
                    this.right = new TreeNode(x);
                }
            }
        }

        public int search (int x){
            if(this.val>x){
                if(this.left!=null) {
                    int leftResult =  this.left.search(x);
                    return leftResult==-1? this.val : leftResult;
                } else {
                    return this.val ;
                }
            } else {
                if(this.right!=null) {
                    return this.right.search(x);
                } else {
                    return -1;
                }
            }

        }

    }

    public int[] findNext(int[] A, int n) {
        // write code here
        int[] result = new int[n] ;
        result[n-1] = -1;
        TreeNode root = new TreeNode(A[n-1]);
        for(int i=n-2; i>=0; i--){
            root.build(A[i]);
            result[i] = root.search(A[i]);
        }
        return result ;
    }
}

利用了一个查找树

发表于 2019-11-14 16:49:58 回复(0)

下一个较大元素II

问题信息

热门推荐

通过挑战的用户

相关试题