单调栈

单调栈

🟧概述

🔻含义：栈底到栈顶维持一个单调有序的栈

单调栈就是栈里的数据递增或递减存放，也就是要做到有序，如果待入栈数据不符合栈里数据的有序性，则栈顶出栈，一直到栈里数据有序，最后将当前遍历到的元素栈插入到栈顶。

我们将当前还没得到答案的下标暂存于栈内，从而实现「被动」更新答案。也就是说，栈内存放的永远是还没更新答案的下标。

每次将当前遍历到的下标存入栈内，将当前下标存入栈内前，检查一下当前值是否能够作为栈内位置的答案（即成为栈内位置的「下一个更大的元素」），如果可以，则将栈内下标弹出。

求最近的最大值使用 递减栈 反之最大栈 - >max = Math.max(max,temp);max=Integer.MIN_VALUE;

🔻试用场景： 找最近一个比当前值大或者小的左边和右边的坐标 空间优化时间

🔻时间复杂度： O(n²) ->O(n)

🔻空间复杂度： O(n)

🔻注意事项：

🔸遍历初始化的数组

🔸遍历方向:首遍历还是尾遍历

🔸栈的单调性选择：降序还是升序

🔸放入栈的是值：是放入下标还是下标对应的值

🔸内循环比较：一定是比较下标对应的值 如果 存入的是值 那就不用

🟧模板

📌降序栈：求最近的最大值

class Solution {
		//底部到顶部 依次递减
    public int[] deSeqStack(int[] nums) {
        int len = temperatures.length;

        Deque<Integer> stack = new LinkedList();

        for(){

            while(!stack.isEmpty()&&nums[i]>nums[stack.peek()]){
                int preIdx = stack.poll();
	              handle();
            }

             stack.push(i);
        }

    }
}

📌 升序栈：求最近的最小值

class Solution {
		//底部到顶部 依次递减
    public int[] seqStack(int[] nums) {
        int len = temperatures.length;

        Deque<Integer> stack = new LinkedList();

        for(){

            while(!stack.isEmpty()&&nums[i]<nums[stack.peek()]){
                int preIdx = stack.poll();
	              handle();
            }

             stack.push(i);
        }

    }
}

🟧总结

🔻思考1:为什么单调栈能避免暴力搜索？

🔸使用空间换时间的方式去优化 额外维护一个单调栈 栈内记录元素下标 作为零时缓存 这个缓存是由近及远的 在第二个循环去缓存中 判断当前元素是否符合题意

🔸根据模板 第二层循环也是没有遍历原来的数组 而是遍历栈的零时缓存 将O(n²) 降为 数组和栈的O(n) 遍历

🔻思考2:单调栈本质？

🔸单调栈本质上来源于单调性，一般可以理解为 当遍历到的元素的 不符合单调性的时候 拿他和栈顶元素比较 如果一直不符合 就一直栈顶元素出栈 直到符合预期

🔻思考3:单调栈实际应用？

🔸暂无

🔻思考4:单调栈的限制条件？

🔸空间O(n)