下一个更大元素 IV
难度:
标签:
题目描述
代码结果
运行时间: 138 ms, 内存: 28.4 MB
/*
* 思路：
* 使用Java Stream API来解决这个问题并不直观，因此我们会首先尝试常规方法来找到所有第二大元素的位置，然后通过Stream API输出结果。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class Solution {
public int[] secondGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1); // 初始化为-1
for (int i = 0; i < n; i++) {
boolean foundFirst = false;
for (int j = i + 1; j < n; j++) {
if (nums[j] > nums[i]) {
if (foundFirst) {
result[i] = nums[j];
break;
}
foundFirst = true;
}
}
}
return IntStream.of(result).toArray(); // 使用Stream API转换结果数组
}
}解释
方法:
这个题解采用了单调栈的技巧来找出每个元素的第二大元素。核心思想是使用两个栈 st1 和 st2，以及一个辅助栈 tmp。st1 用来存放遍历到的元素的下标，保证栈顶到栈底元素是单调递减的。st2 用于记录第一个大于栈内元素的下标，以便在找到第二个大于栈内元素时，快速进行更新。当遇到一个新元素 n 时，如果它大于 st2 栈顶元素所对应的值，说明找到了一个更大的第二元素，将其更新到结果数组 res 中。之后，如果新元素 n 大于 st1 栈顶元素，将这些元素移动到 tmp，因为需要继续寻找这些元素的第二大元素。最后，将遍历到的元素下标 i 压入 st1，并将 tmp 中元素转移回 st2，保持 st1 和 st2 的有效性。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在单调栈使用中，为什么选择在遇到一个新元素大于st1栈顶元素时，将其移至临时栈tmp中而不是直接处理或丢弃？
▷🦆
算法中如何确保每个元素的第二大值只被更新一次，而不会因为后续元素再次更新导致错误？
▷🦆
st2栈的具体作用是什么，它与st1栈在维护过程中有哪些不同的点？
▷🦆
为什么在最后处理完所有元素后，不需要对st1或st2中剩余的元素进行特殊处理？
▷