一、啥是下一个更大元素问题
咱先来说说下一个更大元素问题是啥。简单来讲，就是给你一个数组，对于数组里的每个元素，你要找出在它右边第一个比它大的元素。要是右边没有比它大的元素，那就用 -1 来表示。
举个例子哈，有个数组 [2, 1, 2, 4, 3]。对于第一个元素 2 来说，它右边第一个比它大的元素是 4；对于第二个元素 1 来说，右边第一个比它大的元素是 2；第三个元素 2 右边第一个比它大的元素也是 4；第四个元素 4 右边没有比它大的元素，所以是 -1；第五个元素 3 右边没有比它大的元素，也是 -1。所以这个数组对应的下一个更大元素数组就是 [4, 2, 4, -1, -1]。
二、单调栈是个啥
单调栈是一种特殊的栈，它的特点是栈里的元素是单调递增或者单调递减的。咱们解决下一个更大元素问题用的是单调递减栈。啥意思呢，就是栈里的元素从栈底到栈顶是逐渐变小的。
当我们遍历数组的时候，如果当前元素比栈顶元素大，那就说明栈顶元素找到了它右边第一个比它大的元素，这时候就把栈顶元素出栈，并且记录下栈顶元素对应的下一个更大元素就是当前元素。然后继续比较当前元素和新的栈顶元素，直到当前元素小于等于栈顶元素，再把当前元素入栈。
三、单调栈解决下一个更大元素问题的代码实现（Java 技术栈）
import java.util.Arrays;
import java.util.Stack;
public class NextGreaterElement {
public static int[] nextGreaterElements(int[] nums) {
int n = nums.length;
// 用于存储结果的数组，初始值都设为 -1
int[] result = new int[n];
Arrays.fill(result, -1);
// 创建一个栈
Stack<Integer> stack = new Stack<>();
// 遍历数组
for (int i = 0; i < n; i++) {
// 当栈不为空且当前元素大于栈顶元素时
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
// 栈顶元素出栈
int index = stack.pop();
// 记录栈顶元素对应的下一个更大元素
result[index] = nums[i];
}
// 当前元素入栈
stack.push(i);
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 1, 2, 4, 3};
int[] result = nextGreaterElements(nums);
// 输出结果
for (int num : result) {
System.out.print(num + " ");
}
}
}
代码解释
- 首先，我们创建了一个和原数组长度一样的结果数组
result，并且把里面的元素都初始化为 -1。这是因为如果一个元素右边没有比它大的元素，那它对应的下一个更大元素就是 -1。 - 然后，我们创建了一个栈
stack，用来存储数组元素的下标。 - 接着，我们开始遍历数组。对于每个元素，我们检查栈是否为空，并且当前元素是否大于栈顶元素对应的元素。如果是，就把栈顶元素出栈，并且记录下栈顶元素对应的下一个更大元素就是当前元素。
- 最后，把当前元素的下标入栈。
四、应用场景
单调栈解决下一个更大元素问题在很多场景都有用。比如说在股票交易中，我们可以用它来找出某一天之后第一个股票价格比当天高的日子。再比如说在计算柱状图中最大矩形面积的时候，也会用到这个思路。
五、技术优缺点
优点
- 时间复杂度低：单调栈的时间复杂度是 O(n)，因为每个元素最多入栈和出栈一次。这比暴力解法的 O(n^2) 要快很多。
- 代码简洁：代码实现相对简单，只需要一个栈和一个循环就可以解决问题。
缺点
- 适用范围有限：单调栈主要适用于解决下一个更大元素、下一个更小元素这类问题，对于其他类型的问题可能不太适用。
- 理解难度较大：对于初学者来说，单调栈的概念和实现可能比较难理解。
六、注意事项
- 栈里存储的是下标：在实现单调栈的时候，栈里存储的是数组元素的下标，而不是元素本身。这样方便我们记录每个元素对应的下一个更大元素。
- 边界条件：在使用栈的时候，要注意栈为空的情况，避免出现空指针异常。
七、文章总结
通过单调栈，我们可以优雅地解决下一个更大元素问题。单调栈的核心思想就是利用栈的单调性，在遍历数组的过程中，不断地更新每个元素的下一个更大元素。它的时间复杂度低，代码简洁，但是适用范围有限，理解起来也有一定难度。在实际应用中，我们要根据具体的问题来选择合适的算法。
评论