单调栈的定义
单调栈是一种数据结构，它维护了一个元素序列，这个序列在栈内要么单调递增，要么单调递减。在单调栈中，新元素的插入操作会遵循特定的规则：对于单调递增栈，只有当新元素大于或等于栈顶元素时，才能将其压入栈中；对于单调递减栈，则相反，只有当新元素小于或等于栈顶元素时，才能将其压入栈中。这种结构保证了栈内的元素顺序在某种意义上是有序的，从而支持高效的元素插入和查询操作。
单调递增栈
单调递增栈是一种特殊类型的栈，它只允许栈内的元素按照严格递增的顺序排列。在这种栈中，每次新元素被压入栈时，必须满足这个元素大于或等于栈顶的元素。如果新元素不满足这个条件，它将不会被压入栈中。这种栈的使用保证了，从栈顶到栈底，元素的值是单调递增的，即每个元素都大于或等于它下面的所有元素。
单调递增栈常用于处理数组中的元素，以找到特定的序列或模式，例如查找给定数组中每个元素右侧第一个比它大的元素，或者左侧第一个比它小的元素。通过利用单调递增栈的性质，可以在一次遍历中高效地解决这类问题。
下面以一个数组案例来解释单调递增栈的入栈出栈的过程：
739. 每日温度查找比数组元素大的下一个数组元素的下标，栈内元素记录的是前一句的结果。
数组元素为[73,74,75,71,69,72,76,73]
| 第i步 | 数组元素 | 栈内元素 | 记录数组元素大的下一个数组元素的下标 |
|---|---|---|---|
| 1 | 73 | 0 | 0，0，0，0，0，0，0，0 |
| 2 | 74 | 1 | 1，0，0，0，0，0，0，0 |
| 3 | 75 | 2 | 1，1，0，0，0，0，0，0 |
| 4 | 71 | 2，3 | 1，1，0，0，0，0，0，0 |
| 5 | 69 | 2，3，4 | 1，1，0，0，0，0，0，0 |
| 6 | 72 | 2，3，5 | 1，1，0，0，1，0，0，0 |
| 7 | 72 | 3 ，5 | 1，1，0，2，1，0，0，0 |
| 8 | 76 | 5，6 | 1，1，4，2，1，0，0，0 |
| 9 | 76 | 6 | 1，1，4，2，1，1，0，0 |
| 10 | 73 | 6，7 | 1，1，4，2，1，1，0，0 |
下面是步骤2的图示
单调递减栈
单调递减栈是一种特殊类型的栈，它确保栈内的元素按照严格递减的顺序排列。在这个栈中，每次新元素被压入栈时，必须满足这个元素小于或等于栈顶的元素。如果新元素不满足这个条件，它将不会被压入栈中。这种栈的使用保证了，从栈顶到栈底，元素的值是单调递减的，即每个元素都小于或等于它下面的所有元素。
压栈和出栈过程和上面单调递增栈类似，这里不再赘述！！！
下面写了几道力扣题，方面大家理解：
739. 每日温度
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] arr=new int[temperatures.length];
Stack<Integer> st= new Stack<>();
for(int i=0;i<temperatures.length;i++){
int t=temperatures[i];
while(!st.isEmpty()&&t>temperatures[st.peek()]){
int j=st.pop();
arr[j]=i-j;
}
st.push(i);
}
return arr;
}
}
这个就是应用单调栈存储比下一个元素大的数组下标，具体的解题过程上面已经给出。
496. 下一个更大元素 I
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> stack = new Stack<Integer>();
HashMap<Integer, Integer> hasMap = new HashMap<Integer, Integer>();
int[] result = new int[nums1.length];
for(int num : nums2) {
while(!stack.isEmpty() && stack.peek()<num){
hasMap.put(stack.pop(), num);
}
stack.push(num);
}
for(int i = 0; i < nums1.length; i++) result[i] = hasMap.getOrDefault(nums1[i], -1);
return result;
}
}
和上一题的解法一样
1475. 商品折扣后的最终价格
class Solution {
public int[] finalPrices(int[] prices) {
int[] arr = new int[prices.length];
ArrayDeque<Pair<Integer, Integer>> stack = new ArrayDeque<>();
for (int i = 0; i <= prices.length; i++) {
int price = i == prices.length ? 0 : prices[i];
while (!stack.isEmpty() && stack.peekLast().getKey() >= price) {
Pair<Integer, Integer> pair = stack.removeLast();
arr[pair.getValue()] = pair.getKey() - price;
}
stack.addLast(new Pair<Integer, Integer>(price, i));
}
return arr;
}
}
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] sum = new int[n];
Arrays.fill(sum, -1);
Deque<Integer> stack = new LinkedList<Integer>();
for (int i = 0; i < n * 2 - 1; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i%n]) {
sum[stack.pop()] = nums[i % n];
}
stack.push(i%n);
}
return sum;
}
}
循环查找的话，加一个取余操作进行查找
962. 最大宽度坡
class Solution {
public int maxWidthRamp(int[] nums) {
int num= 0;
int n = nums.length;
Stack<Integer>min = new Stack<>();
min.push(0);
for(int i = 0; i < n; i ++){
if(nums[i] < nums[min.peek()])min.push(i);
}
for(int i = n - 1; i >= 0; i --){
while(!min.isEmpty() && nums[min.peek()] <= nums[i]){
num= Math.max(res,i - min.peek());
min.pop();
}
}
return num;
}
}
不断遍历找到下标相差最大的值。
853. 车队
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
//上同下小数组大，上同下大数组小，上大下小数组大，上小下大数组小
double[] time=new double[target];
for(int i=0;i<position.length;i++){
time[position[i]]=(target-position[i])/(double)speed[i];
}
Deque<Double> stack = new ArrayDeque<>();
for(int i=0;i<target;i++){
if(time[i]>0){
while(!stack.isEmpty()&&time[i]>=stack.peek()){//保证数组中元素从底到顶递减
stack.pop();
}
stack.push(time[i]);
}
}
return stack.size();
}
}