2454-下一个更大元素 IV

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。

如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：

  • j > i
  • 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 = [2,4,0,9,6]
**输出：** [9,6,6,-1,-1]
**解释：**
下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。

示例 2：

**输入：** nums = [3,3]
**输出：** [-1,-1]
**解释：**
由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

前置知识：496. 下一个更大元素 I 。

从左往右遍历 nums，用（递减）单调栈 s 记录元素，如果 x=\textit{nums}[i] 比 s 的栈顶大，则 x 是栈顶的下个更大元素，弹出栈顶。最后把 x 入栈（实际入栈的是下标 i）。

把弹出的元素加到另一个栈 t 中（注意保持原始顺序），后续循环时，如果 y=\textit{nums}[j] 比 t 的栈顶大，则 y 是栈顶的下下个更大元素，记录答案，弹出栈顶。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        ans, s, t = [-1] * len(nums), [], []
        for i, x in enumerate(nums):
            while t and nums[t[-1]] < x:
                ans[t.pop()] = x
            j = len(s) - 1
            while j >= 0 and nums[s[j]] < x:
                j -= 1
            t += s[j + 1:]
            del s[j + 1:]
            s.append(i)
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    private static int[] s = new int[100000], t = new int[100000]; // 由于有一个整体拷贝的过程，用数组模拟栈

    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length, p = 0, q = 0;
        var ans = new int[n];
        Arrays.fill(ans, -1);
        for (var i = 0; i < n; ++i) {
            var x = nums[i];
            while (q > 0 && nums[t[q - 1]] < x)
                ans[t[--q]] = x;
            var pp = p;
            while (p > 0 && nums[s[p - 1]] < x) --p;
            System.arraycopy(s, p, t, q, pp - p);
            q += pp - p;
            s[p++] = i;
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> secondGreaterElement(vector<int> &nums) {
        int n = nums.size();
        vector<int> ans(n, -1), s, t;
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            while (!t.empty() && nums[t.back()] < x) {
                ans[t.back()] = x;
                t.pop_back();
            }
            int j = (int) s.size() - 1;
            while (j >= 0 && nums[s[j]] < x) --j;
            t.insert(t.end(), s.begin() + (j + 1), s.end());
            s.resize(j + 1);
            s.push_back(i);
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func secondGreaterElement(nums []int) []int {
	ans := make([]int, len(nums))
	for i := range ans {
		ans[i] = -1
	}
	s, t := []int{}, []int{}
	for i, x := range nums {
		for len(t) > 0 && nums[t[len(t)-1]] < x {
			ans[t[len(t)-1]] = x
			t = t[:len(t)-1]
		}
		j := len(s) - 1
		for j >= 0 && nums[s[j]] < x {
			j--
		}
		t = append(t, s[j+1:]...)
		s = append(s[:j+1], i)
	}
	return ans
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums 的长度。每个元素至多入栈出栈两次。
  • 空间复杂度：O(n)。
 Comments
On this page
2454-下一个更大元素 IV