class Solution {
public:
vector<int> secondGreaterElement(vector<int>& nums) {
}
};
6227. 下一个更大元素 IV
给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。
如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：
j > inums[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 <= 1050 <= nums[i] <= 109原站题解
rust 解法, 执行用时: 28 ms, 内存消耗: 4 MB, 提交时间: 2023-12-12 00:15:57
impl Solution {
pub fn second_greater_element(nums: Vec<i32>) -> Vec<i32> {
let mut ans = vec![-1; nums.len()];
let mut s = Vec::new();
let mut t = Vec::new();
for (i, &x) in nums.iter().enumerate() {
while !t.is_empty() && nums[*t.last().unwrap()] < x {
ans[t.pop().unwrap()] = x; // t 栈顶的下下个更大元素是 x
}
let mut j = s.len();
while j > 0 && nums[s[j - 1]] < x {
j -= 1; // s 栈顶的下一个更大元素是 x
}
t.extend(s.drain(j..)); // 把从 s 弹出的这一整段元素加到 t
s.push(i); // 当前元素（的下标）加到 s 栈顶
}
ans
}
}
javascript 解法, 执行用时: 240 ms, 内存消耗: 73.1 MB, 提交时间: 2023-12-12 00:15:44
/**
* @param {number[]} nums
* @return {number[]}
*/
var secondGreaterElement = function (nums) {
const n = nums.length;
const ans = Array(n).fill(-1);
const s = [];
const t = [];
for (let i = 0; i < n; i++) {
const x = nums[i];
while (t.length > 0 && nums[t[t.length - 1]] < x) {
ans[t.pop()] = x; // t 栈顶的下下个更大元素是 x
}
let j = s.length - 1;
while (j >= 0 && nums[s[j]] < x) {
j--; // s 栈顶的下一个更大元素是 x
}
t.push(...s.splice(j + 1)); // 把从 s 弹出的这一整段元素加到 t
s.push(i); // 当前元素（的下标）加到 s 栈顶
}
return ans;
};
cpp 解法, 执行用时: 148 ms, 内存消耗: 86.2 MB, 提交时间: 2023-12-12 00:15:31
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 栈顶的下下个更大元素是 x
t.pop_back();
}
int j = s.size();
while (j && nums[s[j - 1]] < x) {
j--; // s 栈顶的下一个更大元素是 x
}
t.insert(t.end(), s.begin() + j, s.end()); // 把从 s 弹出的这一整段元素加到 t
s.resize(j); // 弹出一整段元素
s.push_back(i); // 当前元素（的下标）加到 s 栈顶
}
return ans;
}
};
python3 解法, 执行用时: 348 ms, 内存消耗: 29.3 MB, 提交时间: 2023-12-12 00:15:13
class Solution:
def secondGreaterElement(self, nums: List[int]) -> List[int]:
ans = [-1] * len(nums)
s = []
t = []
for i, x in enumerate(nums):
while t and nums[t[-1]] < x:
ans[t.pop()] = x # t 栈顶的下下个更大元素是 x
j = len(s) - 1
while j >= 0 and nums[s[j]] < x:
j -= 1 # s 栈顶的下一个更大元素是 x
t += s[j + 1:] # 把从 s 弹出的这一整段元素加到 t
del s[j + 1:] # 弹出一整段元素
s.append(i) # 当前元素（的下标）加到 s 栈顶
return ans
java 解法, 执行用时: 10 ms, 内存消耗: 57.9 MB, 提交时间: 2023-08-09 10:17:23
class Solution {
private static int[] s = new int[100000], t = new int[100000]; // 由于有一个整体拷贝的过程，用数组模拟栈。 s 是第一个单调栈，查找右侧第一大元素，t 是第二个单调栈，查找右侧第二大元素
public int[] secondGreaterElement(int[] nums) {
int n = nums.length, p = 0, q = 0;// 分别是两个栈s,t的栈顶
var ans = new int[n];
Arrays.fill(ans, -1);
for (var i = 0; i < n; ++i) {
var x = nums[i];// 遍历nums,将x = nums[i]入栈
while (q > 0 && nums[t[q - 1]] < x) // 当前t栈顶对应nums值小于x
ans[t[--q]] = x;// t[--q]的右侧第二大元素是 x，生成答案，同时弹出栈顶
var pp = p;
while (p > 0 && nums[s[p - 1]] < x) --p;// x是s栈顶右侧第一大，弹出栈顶
System.arraycopy(s, p, t, q, pp - p);//将栈s从p位置开始拷贝`pp-p`个元素到栈t的q下标。这里相当于s弹出的元素都添加到了t的栈顶,因为这部分元素遇到了右侧第一大的数x，现在转移到t第二栈，当这部分元素在t中遇到更大的数，这个更大的数就是这部分元素的右侧第二大数。
q += pp - p;// 更新第二栈t的新栈顶q
s[p++] = i;// 当前元素nums[i]下标i入栈s
}
return ans;
}
}
python3 解法, 执行用时: 360 ms, 内存消耗: 29.2 MB, 提交时间: 2023-08-09 10:19:29
'''
一次遍历 + 双单调栈
从左往右遍历 nums，用（递减）单调栈 s 记录元素，
如果 x=nums[i] 比 sss 的栈顶大，则 x 是栈顶的下个更大元素，弹出栈顶。
最后把 x 入栈（实际入栈的是下标 i）。
把弹出的元素加到另一个栈 t 中（注意保持原始顺序），
后续循环时，如果 y=nums[j] 比 t 的栈顶大，则 y 是栈顶的下下个更大元素，记录答案，弹出栈顶。
'''
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
golang 解法, 执行用时: 120 ms, 内存消耗: 9.1 MB, 提交时间: 2023-08-09 10:20:17
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
}