# 核心原则

及时移除无用数据，保证栈 / 队列的有序性

# 上一个更大元素

采用栈保存递减的元素，即递减栈（弹出的都是小于当前元素的，只保留大于）

若栈顶元素 $\le$ 当前元素 $nums[i]$ ，则弹出栈顶元素直至「栈为空」（左边没有比 $nums[i]$ 大的元素）或者「栈顶元素 $>$ 当前元素 $nums[i]$ 」

此时栈顶的元素就是 $nums[i]$ 上一个更大的元素

例如： $nums:[3,1,2,5,3,4]$

$i = 0,st:[]$ 。栈顶为空此时 $3$ 左边没有比 $3$ 更大的元素， $l[0] = -1$ ，更新 $st:[3]$

$i = 1,st:[3]$ 。此时，栈顶元素 $3 \gt 1$ ，则 $3$ 就是 $1$ 上一个最大的元素， $l[1]=3$ ，更新 $st:[3,1]$

$i=2,st:[3,1]$ 。 $peek =1\le nums[i]=2$ ，弹出栈顶元素 $1$ ，此时 $st:[3]$ 。

由于，栈顶元素 $3 \gt 1$ ，则 $3$ 就是 $2$ 上一个最大的元素， $l[2]=3$ ，更新 $st:[3,2]$

$i=3,st:[3,2]$ 。

$peek =2\le nums[i]=5$ ，弹出栈顶元素 $2$ ，此时 $st:[3]$ 。

$peek =3\le nums[i]=5$ ，弹出栈顶元素 $3$ ，此时 $st:[]$ 。

栈顶为空此时 $5$ 左边没有比 $5$ 更大的元素， $l[3] = -1$ ，更新 $st:[5]$

$i=4,st:[5]$ 。此时，栈顶元素 $5 \gt 1$ ，则 $5$ 就是 $3$ 上一个最大的元素， $l[4]=5$ ，更新 $st:[5,3]$

$i=5,st:[5,3]$ 。 $peek =3\le nums[i]=4$ ，弹出栈顶元素 $3$ ，此时 $st:[5]$ 。

由于，栈顶元素 $5 \gt 4$ ，则 $5$ 就是 $4$ 上一个最大的元素， $l[5]=5$ ，更新 $st:[5,4]$

	class Solution {
	public int[] prevGreaterElement(int[] arr) {
	int n = arr.length;
	//l [i]: 下标 i 左边第一个小于 i 的下标，不存在为 -1
	int[] l = new int[n];
	Deque<Integer> lst = new LinkedList<>();
	// 哨兵
	lst.addFirst(-1);
	for (int i = 0; i < n; i++) {
	while (lst.size() > 1 && arr[lst.peekFirst()] >= arr[i]) {
	lst.pollFirst();
	}
	l[i] = lst.peekFirst();
	lst.addFirst(i);
	}
	return l;
	}
	}

# 下一个更大的元素

下一个最更大的元素也是同理，只不过是倒序遍历

	class Solution {
	public int[] prevGreaterElement(int[] arr) {
	int n = arr.length;
	//r [i]: 下标 i 右边第一个小于等于 i 的下标，不存在为 n
	int[] r = new int[n];
	Deque<Integer> rst = new LinkedList<>();
	// 哨兵
	rst.addFirst(n);
	for (int i = n - 1; i >= 0; i--) {
	while (rst.size() > 1 && arr[rst.peekFirst()] > arr[i]) {
	rst.pollFirst();
	}
	r[i] = rst.peekFirst();
	rst.addFirst(i);
	}
	return r;
	}
	}

而上一个更小的元素则采用的是递增栈（弹出的都是大于当前元素的，只保留小于）

若栈顶元素 $\ge$ 当前元素 $nums[i]$ ，则弹出栈顶元素直至「栈为空」（左边没有比 $nums[i]$ 大的元素）或者「栈顶元素 $<$ 当前元素 $nums[i]$ 」

此时栈顶的元素就是 $nums[i]$ 上一个更小的元素

# 同时计算上一个更大的元素与下一个更大于等于的元素

我们可以在计算 $l[i]$ 的同时计算 $r[i]$ ，若栈顶元素 $peek$ 小于等于 $nums[i]$ ，则说明 $peek$ 的右边第一个大于等于 $peek$ 的元素即为 $nums[i]$

	class Solution {
	public void test(int[] arr) {
	// 3 2 1 4
	int n = arr.length;
	//l [i]: 下标 i 左边第一个小于 i 的下标，不存在为 -1
	int[] l = new int[n];
	//r [i]: 下标 i 右边第一个小于等于 i 的下标，不存在为 n
	int[] r = new int[n];

	// 存放的是递增的元素
	Deque<Integer> st = new LinkedList<>();
	st.addFirst(-1);
	for (int i = 0; i < n; i++) {
	while (st.size() > 1 && arr[st.peekFirst()] <= arr[i]) {
	// 此时弹出的栈顶元素 peek 右边第一个小于等于 peek 的元素为 i
	r[st.pollFirst()] = i;
	}
	l[i] = st.peekFirst();
	st.addFirst(i);
	}
	// 说明还有剩余元素
	while (st.size() > 1) {
	r[st.pollFirst()] = n;
	}
	}
	}

可以合并剩余元素代码

	class Solution {
	public void test(int[] arr) {
	int n = arr.length;
	//l [i]: 下标 i 左边第一个小于 i 的下标，不存在为 -1
	int[] l = new int[n];
	//r [i]: 下标 i 右边第一个小于等于 i 的下标，不存在为 n
	int[] r = new int[n];
	// 存放的是递减的元素
	Deque<Integer> st = new LinkedList<>();
	st.addFirst(-1);
	for (int i = 0; i < n; i++) {
	// 说明还有剩余元素，此时内部都是递减的，其右边界为 n（即右边没有比它大的元素），需要都满足条件
	int x = i == n ? Integer.MAX_VALUE : arr[i];
	while (st.size() > 1 && arr[st.peekFirst()] <= arr[i]) {
	// 此时弹出的栈顶元素 peek 右边第一个小于等于 peek 的元素为 i
	r[st.pollFirst()] = i;
	}
	l[i] = st.peekFirst();
	st.addFirst(i);
	}
	}
	}