Leetcode 2454. 下一个更大元素 IV

• Leetcode 2454. 下一个更大元素 IV
• 题目
  • 给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。
  • 如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：
    • j >
    • nums[j] > nums[i]
    • 恰好存在 一个 k 满足 i < k < j 且 nums[k] > nums[i] 。
    • 如果不存在 nums[j] ，那么第二大整数为 -1 。
    • 比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。
  • 请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。
  • 1 <= nums.length <= 10 ^ 5
  • 0 <= nums[i] <= 10 ^ 9
• 解法
  • 反向思考 + 两次单调队列 + 排序二分/TreeSet：
  • 第 1 步：
  • 题目可以转化为两步处理，
  • 通过下标 i 先找到 i 右边第一个 nums[k] > nums[i] 的 k，
  • 再存储 i 和 k 在找到 k 右边第一个 nums[j] > nums[i] 的 nums[j]
  • 第 2 步：
  • 找 k 可以使用倒序遍历，
  • 然后使用一个严格递减的单调栈，
  • 每次第一个大于 nums[i] 的 nums 下标即为 k，
    • 因为当求 i-1 时，要么 k 就是之前放入的 i(nums[i-1] < nums[i])，要么就是栈里剩下的某个元素(nums[i-1] >= nums[i])
  • 将所有 i 与 k 均存起来，
  • 第 3 步：
  • 由于求 i-1 时，此时的 k1 可能比求 i 时的 k2 更靠右，此时 j1 就应该在 [0,k1) 对应的单调栈中，
  • 在线求特别麻烦，因此可以考虑离线（即将所有 i-k 存起来，排序后统一处理）
  • 第 4 步：
  • 对 k 降序排，然后再次倒序使用一个严格递减的单调栈，
  • 当遍历的值等于某个 k 时，使用 二分/TreeSet 栈中大于 nums[i] 的最小值，即为结果
  • 遍历单调栈与 k 使用类似双指针的方式处理
  • 第 5 步：
  • 时间复杂度：O（n*logn）排序，空间复杂度：O（n）
• 代码

/**
     * 反向思考 + 两次单调队列 + 排序二分/TreeSet：
     *
     * 第 1 步：
     * 题目可以转化为两步处理，
     * 通过下标 i 先找到 i 右边第一个 nums[k] > nums[i] 的 k，
     * 再存储 i 和 k 在找到 k 右边第一个 nums[j] > nums[i] 的 nums[j]
     *
     * 第 2 步：
     * 找 k 可以使用倒序遍历，
     * 然后使用一个严格递减的单调栈，
     * 每次第一个大于 nums[i] 的 nums 下标即为 k，
     *     * 因为当求 i-1 时，要么 k 就是之前放入的 i(nums[i-1] < nums[i])，要么就是栈里剩下的某个元素(nums[i-1] >= nums[i])
     * 将所有 i 与 k 均存起来，
     *
     * 第 3 步：
     * 由于求 i-1 时，此时的 k1 可能比求 i 时的 k2 更靠右，此时 j1 就应该在 [0,k1) 对应的单调栈中，
     * 在线求特别麻烦，因此可以考虑离线（即将所有 i-k 存起来，排序后统一处理）
     *
     * 第 4 步：
     * 对 k 降序排，然后再次倒序使用一个严格递减的单调栈，
     * 当遍历的值等于某个 k 时，使用 二分/TreeSet 栈中大于 nums[i] 的最小值，即为结果
     * 遍历单调栈与 k 使用类似双指针的方式处理
     *
     * 第 5 步：
     * 时间复杂度：O（n*logn）排序，空间复杂度：O（n）
     *
     */
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;

        // 所有 i 与 k 均存起来，k 不存在则使用 -1
        List<Pair<Integer, Integer>> indexList = new ArrayList<>();
        int[] res = new int[n];

        // 找 k 可以使用倒序遍历，然后使用一个严格递减的单调栈，
        Deque<Integer> decreaseStack = new LinkedList<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!decreaseStack.isEmpty() && nums[decreaseStack.peekFirst()] <= nums[i]) {
                decreaseStack.pop();
            }

            indexList.add(new Pair<>(i, decreaseStack.isEmpty() ? -1 : decreaseStack.peekFirst()));
            // k 等于 -1 则结果也为 -1
            res[i] = -1;

            decreaseStack.push(i);
        }

        // 对 k 降序排，然后再次倒序使用一个严格递减的单调栈
        Collections.sort(indexList, (o1, o2) -> o2.getValue() - o1.getValue());
//        System.out.println(indexList);

        // 当遍历的值等于某个 k 时，使用 二分/TreeSet 栈中大于 nums[i] 的最小值，即为结果
        TreeSet<Integer> treeSet = new TreeSet<>();
        decreaseStack.clear();

        int listIndex = 0;
        for (int i = n - 1; i >= 0 && listIndex < n; i--) {
            while (listIndex < n && i == indexList.get(listIndex).getValue()) {
                int numsIndex = indexList.get(listIndex).getKey();

                Integer resTemp = treeSet.higher(nums[numsIndex]);
                res[numsIndex] = resTemp == null ? -1 : resTemp;

                listIndex++;
            }

            while (!decreaseStack.isEmpty() && nums[decreaseStack.peekFirst()] <= nums[i]) {
                treeSet.remove(nums[decreaseStack.peekFirst()]);
                decreaseStack.pop();
            }

            treeSet.add(nums[i]);
            decreaseStack.push(i);
        }

        return res;
    }