我要招人

去企业版

首页 > 试题广场 >

n个整数的无序数组，找到每个元素后面比它大的第一个数，要求时

[问答题]

n个整数的无序数组，找到每个元素后面比它大的第一个数，要求时间复杂度为O(N)

查看答案及解析

轻澄

插入一个简单易懂的解答：https://blog.csdn.net/rjszz1314/article/details/103929927

发表于 2021-03-31 21:47:17 回复(0)

jiangziben

if(num.empty())

return num;

vector<int> res(num.size());

        stack<int> temp;
        for (int i = 0; i < num.size()-1; i++)
        {
            if (num[i]>= num[i+1])
            {
                temp.push(i);
            }
            else
            {
                res[i] = num[i+1];
                while (!temp.empty() && num[temp.top()] < num[i+1])
                {
                    res[temp.top()] = num[i+1];
                    temp.pop();
                }

}

发表于 2019-08-16 22:30:26 回复(0)

王钲超

def first_larger_number(arr):
    #假设，第2个数比第1个数字，那么第3个数字要先比第二个数字大才能比第1个数字大
    r = [-1 for i in arr]
    stack = []
    for i, e in enumerate(arr):
        while stack != [] and e > stack[-1][1]:
            tmp = stack.pop()
            r[tmp[0]] = e
        stack.append([i,e])
    return r

发表于 2021-07-26 10:01:08 回复(0)

眺望北方

package com.test.day01;

/*
@author YG
@create 2021/3/17   22:04
*/

import java.util.Stack;

public class test {
  public static void main(String[] args) {
      int[] a = {100,5, 3, 2, 4, 11};
      int[] result = func(a);
      for (int i = 0; i < a.length; i++) {
          if (result[i] == -1) {
              System.out.println("null");
          } else {
              System.out.println(a[result[i]]);
          }
      }
  }

  public static int[] func(int[] array){
      int length = array.length;
      Stack<Integer> stack = new Stack<Integer>();
      int[] result = new int[length];
      int i = 0;
      while(i<length){
          if(stack.isEmpty()){
              stack.push(i);
              i++;
              continue;
          }
          if (array[stack.peek()]>array[i]){
              stack.push(i);
              i++;
              continue;
          }
          int top = stack.pop();
          result[top]=i;
      }
      while (!stack.isEmpty()){
         int top = stack.pop();
         result[top] = -1;
      }
      return result;
  }
}

发表于 2021-03-17 22:35:01 回复(0)

不会真有人不僵硬吧

Java代码：

public class Main{
    public static void main(String[] args) throws Exception{
        int[] a = new int[]{2,1,3,2,5};
        int[] ans = new int[a.length];
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<a.length-1;i++){
            if(a[i] >= a[i+1]){
                stack.push(i);
            }else{
                ans[i] = a[i+1];
                while(!stack.isEmpty() && nums[stack.peek()] < a[i+1]){
                    ans[stack.peek()] = a[i+1];
                    stack.pop();
                }
            }
        }
        for(Integer an:ans){
            System.out.println(an);
        }
    }
}

编辑于 2021-03-16 17:43:14 回复(0)

找实习冲冲冲

#include <bits/stdc++.h>
using namespace std;

vector<int> find1(vector<int>num)
{
    if(num.size() == 0) return {};
    vector<int> res(num.size(),-1);
    stack<int> s;
    int i = 0;
    while(i < num.size())
    {
        if(s.empty() || num[s.top()] >= num[i])     s.push(i++);//当前元素比栈顶元素小，加入单调栈中
        else        
        {
            res[s.top()] = num[i]; //当前元素是栈顶元素后面的第一个较大元素，加入结果中
            s.pop();
        }
    }
    return res;
}

int main()
{
    vector<int> num = {1, 3, 2, 4, 99, 101, 5, 8};
    vector<int> res = find1(num);
    for(auto i : res)
        cout << i << "  ";
    return 0;
}

发表于 2021-01-30 11:23:16 回复(0)

机械暴龙兽丶

vector<int> FindFirstBig(vector<int> num)

{

vector<int> res(num.size());

if(num.size() == 0)

return res;

stack<int> s;

int i = 0;

while(i < num.size())

{

if(s.empty() || num[s.top()] >= num[i])

{

s.push(i);

}

else{

res[s.top()] = num[i];

s.pop();

}

while(!s.empty())

{

res[s.pop()] = INT_MAX;

s.pop();

}

return res;

}

发表于 2019-07-25 14:46:03 回复(0)

又毕不了业了

vector<int> findMax(vector<int>num)
{
    if(num.size()==0)
         return num;
     vector<int>res(num.size());
    int i=0;
     stack<int>s;
    while(i<num.size())
    {
        if(s.empty()||num[s.top()]>=num[i])
        {
            s.push(i++);
        }
        else
        {
            res[s.top()]=num[i];
            s.pop();
        }
    }
    while(!s.empty())
    {
        res[s.top()]=INT_MAX;
        s.pop();
    }
    return res;
}

发表于 2019-07-17 16:44:07 回复(0)

提交观点

问题信息

上传者：小小

难度：

8条回答 125收藏 2842浏览

n个整数的无序数组，找到每个元素后面比它大的第一个数，要求时

问题信息

热门推荐

相关试题