本文共 2766 字，大约阅读时间需要 9 分钟。

问题描述:

对于一个数组，找到每个数后面第一个比它大的数。如果不存在就返回-1，通过一个新数组返回1

解决方案:

使用一个栈，栈中保存数组的下标。遍历原数组，如果原数组的值比栈顶下标元素值小，直接入栈，不然的话就一直出栈，并且填写新数组栈顶下标位置为原数组当前访问值，出栈后再进行比较，如果栈中最后海油其他元素，则全部弹出，然后他们的位置填写-1。

package Array;import java.util.Stack;public class FindNextBigger {    /**     * 问题描述:找出数组中后面第一个比它小的数     * 方法:使用一个栈，压入的是元素的下标，如果比栈顶下标的元素小就入栈，不然就一直出栈，直到比栈顶下标元素小。     */     public static int[] findNextBigger(int[] arr){          if(arr == null || arr.length == 1){               return arr;          }          int[] newArr = new int[arr.length];          Stack
   
     stack = new Stack<>();          for(int i = 0; i < arr.length; i++){               if(stack.empty() || arr[i] <= arr[stack.peek()]){                    stack.push(i);               }else{                    while(!stack.empty() && arr[i] > arr[stack.peek()]){                         newArr[stack.pop()] = arr[i];                    }                    stack.push(i);               }          }          while(!stack.empty()){               newArr[stack.pop()] = -1;          }          return newArr;     }     public static void main(String[] args){          int[] arr = {3,1,2,4};          int[] newArr = findNextBigger(arr);          for(int i = 0; i < arr.length; i++){               System.out.print(newArr[i] + " ");          }          System.out.println();     }}
   

另一种情况:

1、假如说是一个数组nums1是另一个数组nums2的子集，求出nums1在nums2中右边第一个比它大的数

方法:也是使用一个栈，遍历nums1,然后如果栈为空，或者遍历的元素比栈顶元素小的话，就把当前访问元素入栈，注意：

然后再使用一个哈希表，如果遍历的当前元素比栈顶大，则弹出栈顶元素，并把它放到HashMap的key中，然后value部分放当前元素。这样遍历完数组nums2,HashMap中保存的就是有右边比它大的数的元素，而栈中剩下的元素都是右边没有比它大的元素。

这样的话，填写输出数组，只要访问一下HashMap表，如果HashMap中没有这个元素，那么就是-1，如果有的话就是取出HashMap对应的value,所以时间复杂度就是O(n)，因为nums2数组中元素每个都会被遍历一次，每个都会入栈一次，最多出栈一次，也有可能不出栈，所以时间复杂度就是O(n).填写输出数组的时间复杂度是O(nums1.length)，

空间复杂度也是O(n）

class Solution {    public int[] nextGreaterElement(int[] nums1, int[] nums2) {        if(nums1 == null){           return null;         }         Stack
   
     stack = new Stack<>();         HashMap
    
      map = new HashMap<>();            int[] ans = new int[nums1.length];         if(nums1.length == 0){             return ans;         }         stack.push(nums2[0]);         for(int i = 1; i < nums2.length; i++){             if(nums2[i] <= stack.peek()){                 stack.push(nums2[i]);              }else{                 while(!stack.isEmpty() && nums2[i] > stack.peek()){                     map.put(stack.pop(),nums2[i]);                 }                 stack.push(nums2[i]);                              }         }                        for(int i = 0; i < nums1.length; i++){            if(map.containsKey(nums1[i])){                ans[i] = map.get(nums1[i]);            }else{                ans[i] = -1;            }         }        return ans;    }}
    
   

转载地址：http://vnzji.baihongyu.com/