给你一个数组[2,1,2,4,3]，你返回数组 [4,2,4,−1,−1]

给你一个数组 [2,1,2,4,3] ，你返回数组 [4,2,4,−1,−1]

解释：
第一个 2 后面比 2 大的数是 4 ; 1 后面比 1 大的数是 2 ；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1 ；3 后面没有比 3 大的数，填 -1 。

const arr = [2, 1, 2, 4, 3];
function test(arr) {
  let len = arr.length;
  let left = 0;
  let right = len - 1;
  const result = [];
  let myBeIndex;
  let inserted = false;
  for (let i = 0; i < arr.length; i++) {
    const element = arr[i];
    left = i + 1;
    right = len - 1;
    inserted = false;
    while (left <= right) {
      if (arr[left] > element) {
        result.push(arr[left]);
        inserted = true;
        right = len - 1;
        break;
      }
      if (arr[right] > element) {
        myBeIndex = right;
      }
      left++;
      right--;
    }

    if (myBeIndex) {
      result.push(arr[myBeIndex]);
      inserted = true;
      myBeIndex = null;
    }
    if (!inserted) {
      result.push(-1);
    }
  }
  return result;
}

console.log(test(arr));

function arrFormat(arr){
  let _arr = []
  for (let index = 0; index < arr.length; index++) {
    const val = arr[index];
    //找出这个值之后的数组
    const afterArr = arr.slice(index,arr.length)
    //找出第一个最大值的index
    const firstBiggerIndex = afterArr.findIndex(afterVal=>{
      return afterVal > val
    })
    if(firstBiggerIndex > -1){
      _arr.push(afterArr[firstBiggerIndex])
    }else{
      _arr.push(-1)
    }
  }
  console.log('_arr',_arr)
  return _arr
}
arrFormat([2,1,2,4,3])

时间复杂度O(n)
空间复杂度L(n)

function arrFormat(arr: number[]): number[]{
    const len: number = arr.length;
    const stack: number[] = [arr[0]];
    const ret: number[] = new Array(len).fill(-1);
    const map: Record<number, number[]> = arr.reduce((acc: Record<number, number[]>, key: number, index: number) => {
        if (acc[key]) {
            acc[key].push(index);
        } else {
            acc[key] = [index];
        }
        return acc;
    }, Object.create(null));

    for (let i: number = 1; i < len; i++) {
        const cur = arr[i];
        while (cur > stack[stack.length - 1]) {
            const key: number = stack.pop() as number;
            const index: number = map[key].pop() as number;
            ret[index] = cur;
        }
        stack.push(cur);
    }

    return ret;
}

const arr = [2,1,2,4,3]

const f = arr => {
  if(!arr.length) return []
  const len = arr.length
  let l = 0,
      r = l + 1,
      res = []
  while(res.length < len) {
    let cur = arr[l],
        next = arr[r]
    if(next > cur) {
      res.push(next)
      l += 1
      r = l + 1
    }else if(r >= len - 1){
      res.push(-1)
      l += 1
      r = l + 1
    }else {
      r += 1
    }
  }
  return res
}

const result = f(arr)

console.log(result)

// 暴力法
function test (ary) {
  let result = []
  for(let i = 0; i < ary.length; i++) {
    let value = ary[i]
    let j = i + 1
    while(j < ary.length) {
      if(ary[j] > ary[i]) {
        result.push(ary[j])
        break
      }else {
        j++
     }
    }
    if(!result[i]){
      result[i] = -1
    }
  }
  return result
}
console.log(test([2,1,2,4,3]))

var nextGreaterElement = function(nums1, nums2) {
 //整体思路：
 //1.维护一个单调递减的栈，如果遇到比栈顶大的元素就是第一个比自己大的了
 //2.那么用key表示当前的数，nums[i]表示比key大的第一个数
 //3.枚举nums1找存在的key里的value值即可
  let map = new Map()
  let res = []
  let m = nums2.length
  let stack = []
  for(let i = 0; i < m; i++){
    //栈顶元素存在，并且当前的元素大于栈顶  
    while(stack.length && nums2[i] > stack[stack.length - 1]){
      map.set(stack.pop(), nums2[i]) 
    }  
    stack.push(nums2[i])
  }
  //栈内还有元素，说明后面没有比自己小的了
  while(stack.length){
    map.set(stack.pop(), -1)
  }
  nums1.forEach(item => {
    res.push(map.get(item))
  })
  return res
};

const arr = [2, 1, 2, 4, 3];

const result = arr.map((m, index) => {
  const t = arr.slice(index).find(n => n > m);
  return t === undefined ? -1 : t;
});

console.log(result);

这个应该放在数据结构「栈」里，这道题其实考察的是单调栈，原题其实是 LeetCode 503: 下一个更大元素 II

这个应该放在数据结构「栈」里，这道题其实考察的是单调栈，原题其实是 LeetCode 503: 下一个更大元素 II

function nextGreaterElements(nums: number[]): number[] {
    let stack: number[] = [];
    let res: number[] = new Array(nums.length).fill(-1);
    let len = nums.length;

    for(let i = 2 * len - 1; i >= 0; i--) {
        while(stack.length !== 0 && stack[stack.length - 1] <= nums[i % len]) {
            stack.pop();
        }
        res[i % len] = stack.length === 0 ? -1 : stack[stack.length - 1];

        stack.push(nums[i % len]);
    }

    return res;
};

var nextGreaterElements = function (nums) {
    let res = new Array(nums.length).fill(-1)
    let stack = []
    stack.push(0)
    let numsLen = nums.length
    for (let i = 1, len = nums.length; i < len; i++) {
        while (stack.length && nums[i ] > nums[stack[stack.length - 1]]) {
            res[stack[stack.length - 1]] = nums[i]
            stack.pop()
        }
        stack.push(i)
    }
    return res
};

function getFistMax(nums){
    let res = new Array(nums.length).fill(-1)
    let stack = []
    for(let i=0;i<nums.length;i++){
        while(stack.length&&nums[i]>nums[stack[stack.length-1]]){
            let top = stack.pop()
            res[top] = nums[i]
        }
        stack.push(i)
    }
    return res 
}
console.log(getFistMax([2,1,2,4,3]))

Navigation Menu

Repository navigation

给你一个数组[2,1,2,4,3]，你返回数组 [4,2,4,−1,−1] #142

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

给你一个数组[2,1,2,4,3]，你返回数组 [4,2,4,−1,−1] #142

Description

Activity

gaowujian commented on Dec 28, 2020

hundren commented on Dec 28, 2020

linlinyang commented on Dec 28, 2020

mx52jing commented on Dec 28, 2020

sunsmeil commented on Dec 28, 2020

sunsmeil commented on Dec 28, 2020

yokots commented on Jan 2, 2021

skychx commented on Apr 13, 2021

skychx commented on Apr 13, 2021

xllpiupiu commented on Oct 6, 2021

AlexZhang11 commented on May 24, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions