单调栈
看完此篇:去练下手吧!https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
最常见题型:给定一个数组,找出数组中每个数左边 / 右边比其小且离它最近的数的位置
优化其实在于:对于数组中的某些数,如果 存在 Ax >= Ak,且 Ax在 Ak的右边,那么 Ax就永远不会被用到
因此,当存在这种关系时,可以去将 Ax删除掉,即此时便形成了一个 单调栈 (递增)
基本思想:构建单调栈,每次循环时加入当前数组下标,因为 要将当前数入栈,因此会将栈中大于当前数的元素进行出栈
实际在入栈时,元素既可以是 数组对应元素的下标,也可以是 元素本身
模板
/**
* 数组数组每个数对应其左边最小的那个数的下标,没有的话直接 -1即可
*/
public class SingleStack {
static int[] arr = new int[]{3, 5, 1, 2, 7, 6, 5};
public static void main(String[] args) {
int[] l = new int[arr.length];
Stack<Integer> sl = new Stack<>();
for (int i = 0; i < arr.length; i ++) {
while (!sl.isEmpty() && arr[sl.peek()] >= arr[i]) sl.pop();
if (sl.isEmpty()) l[i] = -1;
else l[i] = sl.peek();
sl.push(i);
}
for (int i = 0; i < l.length; i ++) {
System.out.println(l[i]);
}
}
}