- 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）
- 代码
public int[] secondGreaterElement(int[] nums) {int n = nums.length;List<Pair<Integer, Integer>> indexList = new ArrayList<>();int[] res = new int[n];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()));res[i] = -1;decreaseStack.push(i);}Collections.sort(indexList, (o1, o2) -> o2.getValue() - o1.getValue());
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;}
