【LeetCode】下一个更大元素（I、II、III）

（一）下一个更大元素 I

题目描述：

给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。

示例 :

	输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
	输出: [-1,3,-1]
	解释:
    	对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    	对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
    	对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

解题思路：单调栈+哈希表

本题的主要解题思路是单调栈。首先我们应该注意到nums1是nums2的子集，因此，我们可以首先忽略nums1，而是对 nums2 中的每一个元素，求出其下一个更大的元素。随后对于将这些答案放入哈希映射（HashMap）中，再遍历数组 nums1，利用哈希表的查找优势直接找出答案。

而如何查找nums2中的下一个更大元素，这里主要的思想是单调栈，首先把第一个元素 nums2[1] 放入栈，随后对于第二个元素 nums2[2]，如果 nums2[2] > nums2[1]，那么我们就找到了 nums2[1] 的下一个更大元素 nums2[2]，此时就可以把 nums2[1] 出栈并把 nums2[2] 入栈；如果 nums2[2] <= nums2[1]，我们就仅把 nums2[2] 入栈。对于第三个元素 nums2[3]，此时栈中有若干个元素，那么所有比 nums2[3] 小的元素都找到了下一个更大元素（即 nums2[3]），因此可以出栈，在这之后，我们将 nums2[3] 入栈，以此类推。

相当于我们维护了一个单调不增（从栈顶到栈顶）的栈，换言之，每次考察一个元素，而栈中的数如果比其小，那么该元素就是这些数对应的下一个元素，因此保持单调性即可找到所有要求的值。

代码实现：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //单调栈+哈希表
        int[] res=new int[nums1.length];
        Stack<Integer> stack=new Stack<>();
        Map<Integer,Integer> map=new HashMap<>();

        for(int i=0;i<nums2.length;i++){
            while(!stack.isEmpty() && stack.peek()<nums2[i]){
                map.put(stack.pop(),nums2[i]);
            }
            stack.push(nums2[i]);
        }

        for(int i=0;i<nums1.length;i++){
            res[i]=map.getOrDefault(nums1[i],-1);  //哈希表中没有出现的代表没有下一个最大元素，返回-1
        }
        return res;
    }
}

（二）下一个更大元素 II

题目（Medium）：503. 下一个更大元素 II

题目描述：

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

	输入: [1,2,1]
	输出: [2,-1,2]
	解释: 第一个 1 的下一个更大的数是 2；
	数字 2 找不到下一个更大的数； 
	第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

解题思路：单调栈+两次遍历+存索引

本题和上一题基本类似，所不同的是这里给定的是一个循环数组，当然同样还是利用单调栈的思路，但是这里关键是需要对数组进行两次遍历，因为两次遍历的效果等同于循环数组，这不难理解。

还有一点需要注意的是为了避免重复元素和进行两次遍历，这里我们应该在单调栈中保存数组元素的索引值。

代码实现：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        //单调栈 遍历两遍+存索引
        int[] res=new int[nums.length];
        Stack<Integer> stack=new Stack<>();

        for(int i=0;i<res.length;i++)  //全部初始化为-1
            res[i]=-1;

        for(int i=0;i<nums.length*2;i++){  //关键：两次遍历，存索引
            while(!stack.isEmpty() && nums[stack.peek()]<nums[i%nums.length]){
                res[stack.pop()]=nums[i%nums.length];
            }
            stack.push(i%nums.length);
        }
        
        return res;
    }
}

（三）下一个更大元素III

题目（Medium）：556. 下一个更大元素 III

题目描述：

给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。

示例 1:

输入: 12
输出: 21

示例 2:

输入: 21
输出: -1

解题思路：下一个排列

本题和以上两题略有不同，因为这相当于求一个字符数组的下一个排列的问题，具体解法应该参考求下一个排列的思路。总体来说，分为三步：1、从后往前找到第一个开始减小的数字位置i 2、以该位置为基准，在其后找到刚好比其略大的数字位置j ，然后二者交换 3、将之后的序列反转。

具体可以参见代码实现，而本题可以将整数转化为字符串，进而变为字符数组，从而使用以上的方法。

代码实现：

class Solution {
    public int nextGreaterElement(int n) {
        char[] charArr=String.valueOf(n).toCharArray();
        //从后往前找到第一个开始减小的数
        int i=charArr.length-2;
        while(i>=0 && charArr[i]>=charArr[i+1])
            i--;
        
        if(i<0)  //整体递减
            return -1;
        
        //找到i之后刚好大于charArr[i]的值
        int j=charArr.length-1;
        while(j>=i && charArr[j]<=charArr[i])
            j--;

        swap(charArr,i,j);
        reverse(charArr,i+1,charArr.length-1);
        
        try{
            return Integer.parseInt(new String(charArr));
        }catch(Exception e){
            return -1;
        }
    }

    public void swap(char[] charArr,int i,int j){
        char temp=charArr[i];
        charArr[i]=charArr[j];
        charArr[j]=temp;
    }
    public void reverse(char[] charArr,int begin,int end){
        int i=begin,j=end;
        while(i<j){
            swap(charArr,i,j);
            i++;
            j--;
        }
    }
}

总结：

这三道关于求下一个更大元素的题目，首先需要很好的对题意进行理解，理清题目真正含义是关键，然后再解题思路中我们主要用到的是单调栈的思想，也体现了栈的妙用，而第三题于下一个排列联系起来，是很有代表性的三道算法题。