LeetCode刷题【503】下一个更大元素 II

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

示例 1:

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

注意: 输入数组的长度不会超过 10000。

题解

找某个值附近的前面或者后面的较大或者较小值，最直接的单调栈解法，遍历数组，把当前值存入栈，如果当前值比栈顶值大，则挨个弹出栈顶的值，直到栈顶的值比当前值小，这些挨个被弹出的值可以理解为是当前值前面按照递减顺序排列的值，所以当前值是栈内弹出的这些值的后面的第一个比当前值大的。

然后这里有个变种，题中说了这是一个环状结构，常规作法，破环成链，把链复制一份连接到结尾，变成一个双倍的长度的结构

import java.util.Arrays;
import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res,-1);
        int[] doubleArr = new int[nums.length*2];
        for (int i = 0; i < nums.length; i++) {
            doubleArr[i] = nums[i];
            doubleArr[i+nums.length] = nums[i];
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < doubleArr.length; i++) {
            if (stack.isEmpty()){
                stack.push(i);
            }else{
                while (!stack.isEmpty() && doubleArr[i] > doubleArr[stack.peek()]){
                    res[stack.pop()%nums.length] = doubleArr[i];
                }
                stack.push(i);
            }
        }

        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

上面的是单调栈，常规来说，普通的思路用暴力解法也可使，看力扣上有人提交的暴力解法也能提交通过。

挨个遍历当前数组，每到一位，再往后尝试探测找到第一个比当前值大的值，结束后再继续下一位循环。而需要破环成链的作法和上面一样，构建成原来长度双倍的数组，往后探测的时候只要探测到后面一段的相同位置就可以停止了。

其实还有一个细节也许可以考虑，因为数组的连续性，如果是连续递减区间的话，比如【5,4,3,2,1,3,9】，从5到1是一个连续的递减区间，这样的在从5遍历到1的时候，这个连续区间应该是都可以统一调过的，是不是可以维护这样一个连续递减区间的信息，在遍历数组的每一个值的时候，可以根据这个区间的信息来减少探测次数