当前位置：首页 > news >正文

单调栈的理解

news 来源：原创 2024/5/14 10:32:33

单调栈的理解

- 核心代码
- 场景
- - 思考
- 完整代码
- 环形数组
- - 循环数组

单调栈： 单调递增或 单调递减的栈

核心代码

while (!s.empty()&&s.peek()<=nums[i]){s.pop();
}
s.push(nums[i]);

将要放入的元素，与栈内元素依个比较，小于的都出栈，最后将要放入的元素入栈，实现单调功能。

场景

Next Greater Number 问题：给你⼀个数组，返回⼀个等长的数组，对应索引存储着下⼀个更⼤元素，如果没有更⼤的元素，就存-1。
例如：数组 [2,1,2,4,3]，返回数组 [4,2,4,-1,-1]。

思考

可以看作每个元素向后看，看到的第一个大于其自身的元素，即为所求。（这个过程便是核心代码过程，小于其自身的均出栈，直到看到大于其自身的元素。）
采用从后向前方式遍历原始数组（因为是向后看，后面的元素先入栈出栈，前面的元素再入栈。）
在这里插入图片描述

完整代码

static void nextGreater(int[] nums){int[] ans = new int[nums.length];Stack<Integer> s = new Stack<>();for(int i = nums.length-1;i>=0;i--){while (!s.empty()&&s.peek()<=nums[i]){s.pop();}ans[i] = s.empty()?0:s.peek()-i;s.push(nums[i]);}for (int i : ans) {System.out.printf("%d ",i);}}

环形数组

同样是 Next Greater Number，现在假设数组是个环形的，如何处理？
在这里插入图片描述

循环数组

可通过 % 取模符号实现环形效果。
例如

int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {print(arr[index % n]);index++;
}

本场景中，可看作原始数组的两倍数组，从而实现不仅向后看，也向前看（即将向前看，通过把前面的数字放到后面达到向前看的效果）
在这里插入图片描述
但是可以不用构造双倍数组，而是利用循环数组的技巧进行模拟。(for循环可以按照两倍数组来向一下，只不过去看具体值的时候使用nums[i%size]，即循环数组方式来看)

static int[] nextGreater(int[] nums){int size = nums.length;int[] ans = new int[size];Stack<Integer> s = new Stack<>();for (int i = 2*size-1; i>=0; i--){while (!s.empty() && s.peek()<=nums[i % size]){s.pop();}ans[i % size] = s.empty()?-1:s.peek();s.push(nums[i % size]);}return ans;}```