[leetcode] Next Greater Element

今天处理一下一系列题目：Next Greater Element系列。

---

Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

1. All elements in nums1 and nums2 are unique.
2. The length of both nums1 and nums2 would not exceed 1000.

问题一是基础，翻译一下是这样：两个数组nums1是nums2的子集，而且nums2中各个数字都不重复。然后要求找nums1中的数字在nums2中的位置以右，是否还有比这个数字更大的数，要是有保存下来，要是没有就是-1。

思路也比较清楚，第一个想法肯定是两次遍历，但是肯定是最差的想法，我也就没有写。第二个思路，因为提到nums2中每个数字不重复，很容易联想到map，所以这个思路就是用map记录nums2中每个元素的位置，然后nums1中的元素去找的时候起始点就比较明确了。代码如下：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        Map<Integer,Integer> map = new HashMap<>();
        for ( int i = 0 ; i < nums2.length ; i ++ ) map.put(nums2[i],i);
        for ( int i = 0  ; i < nums1.length ; i ++ ){
            for ( int j = map.get(nums1[i]) ; j < nums2.length ; j ++ ){
                if ( nums2[j] > nums1[i] ) {
                    res[i] = nums2[j];
                    break;
                }else res[i] = -1;
            }
        }
        return res;
    }
}

      运行时间3ms，击败99.95%的提交。应该是现在能优化的最优的方法了。

---

Next Greater Element II

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.

Note: The length of given array won't exceed 10000.

现在题目变了一下，翻译一下：给一个数组nums，这个数组是一个循环数组，也就是最后一个元素的下一个元素是第一个元素。要求找数组中每个元素的next greater element（定义和上面题目一样）。

 第一个思路：根据循环数组的定义，我们可以再定义一个长度为nums.length*2的数组，然后问题就简单了。代码如下：

class Solution {
   public int[] nextGreaterElements(int[] nums) {
        int[] array = new int[nums.length*2];
        int[] res = new int[nums.length];
        for ( int i = 0 ; i < nums.length ; i ++ ) {
            array[i] = nums[i];
            array[i+nums.length] = nums[i];
        }
        for ( int i = 0 ; i < nums.length ; i ++ ){
                for (int j = i; j < array.length; j++) {
                    if (array[j] > nums[i]) {
                        res[i] = array[j];
                        break;
                    } else{
                        res[i] = -1;
                    }
                }
        }
        return res;
    }
}

      运行时间46ms，击败74.06%提交。

---

 Next Greater Element III

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer nand is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

 现在问题又发生了变化，给一个32bit的整数n，要求在组成n的这些数字里面，一个greater element。比如：134，有很多种数字组织办法：134、143、314、341、413、431，那么就返回143。

首先想到的就是要对1、3、4这几个数字进行全排列，然后再找最近的最大数。代码如下：

class Solution {
    int mintoplus = Integer.MAX_VALUE;
    public int nextGreaterElement(int n) {
        String s = String.valueOf(n);
        char[] array = s.toCharArray();
        perm(array,n,0,array.length-1);
        if ( mintoplus == Integer.MAX_VALUE ) return -1;
        return n+mintoplus;
    }
    private void perm(char[] a,int n ,int cur, int end ){
        if ( cur == end ){
            int toplus;
            try {
                toplus = Integer.valueOf(String.valueOf(a)) - n;
                if ( toplus > 0 )  mintoplus = Math.min(mintoplus,toplus);
            }catch (Exception e){
                mintoplus = Integer.MAX_VALUE;
            }
        }else {
            for ( int i = cur ; i <= end ; i ++ ){
                swap(a,cur,i);
                perm(a,n,cur+1,end);
                swap(a,cur,i);
            }
        }
    }
    private void swap(char[] s, int cur, int i) {
        char c = s[cur];
        s[cur] = s[i];
        s[i] = c;
    }
}

    mintoplus变量用来保存全排列数字与n的最小差，perm函数递归实现全排列数的生成。结果运行时间高达437ms，好差的算法，分析一下原因，主要是进行全排列太浪费时间了，而且全排列得到的很多结果都是无用的，因此不能使用全排列的方法。

思路二：因为比一个数字且最近一定尽量发生在数字低位，比如1345的greater数是1354，只是十位和个位交换。所以不妨设想从低位到高位寻找。我们以15764321为例：

        1、15764321从低位到高位寻找，找到5比7小，然后index记录5的位置；

        2、对index+1——最后，也就是764321从后往前寻找第一个大于5的数字，也就是76，bigIndex记录6的位置；

        3、交换index和bigIndex位置元素，数组变成16754321，这时候我们需要对754321从小到大排列；

        4、将index+1到最后位置从小到大排列，注意到未排列之前是从大到小顺序，因此只要交换位置就行了。

        以上就是完整的思路，整理代码如下：

class Solution {
    public int nextGreaterElement(int n) {
        String s = n + "";
        char[] array = s.toCharArray();
        int index = -1;

        //下面的代码从低位到高位，寻找低位比高位大的位置。
        for ( int i = array.length - 2 ; i >= 0 ; i -- ){
            if ( array[i] < array[i+1] ) {
                index = i;
                break;
            }
        }
        if ( index == -1 ) return -1;
        //下面的代码寻找index+1----array.length-1中元素比array[index]大的；因为index+1----array.length-1中元素数组是有序的，从大到小
        int bigIndex = index+1;
        for ( int i = array.length - 1 ; i > index ; i -- ){
            if ( array[i] > array[index] ){
                bigIndex = i;
                break;
            }
        }
        //交换元素位置
        swap(array,index,bigIndex);
        //将index+1----array.length-1中的元素从小到大排列
        reverse(array,index+1,array.length-1);
        long l = Long.valueOf(String.valueOf(array));
        return l > Integer.MAX_VALUE?-1: (int) l;

    }

    private void reverse(char[] array, int low, int high) {
        //这里注意到，index+1----array.length-1中的元素是一个从大到小的排列，因此只要颠倒他们顺序就可以了
        while ( low < high ){
            char c = array[low];
            array[low] = array[high];
            array[high] = c;
            low++;
            high--;
        }
    }

    private void swap(char[] array, int start, int end) {
        //实现start位置元素和end位置元素交换位置
        char c = array[start];
        array[start] = array[end];
        array[end] = c;
    }

}

        没有用全排列，从低位到高位寻找的方法非常成功，运行时间2ms，击败99.70%的人。