数据结构-单调栈笔记

我怎么能想到用单调栈呢？ 什么时候用单调栈呢？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

在使用单调栈的时候首先要明确如下几点：

1 单调栈里存放的元素是什么？

单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。

2  单调栈里元素是递增呢？ 还是递减呢？

注意以下讲解中，顺序的描述为 从栈头到栈底的顺序，因为单纯的说从左到右或者从前到后，不说栈头朝哪个方向的话，大家一定比较懵。

这里我们要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

即：如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

每日温度

739. 每日温度 - 力扣（LeetCode）

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 初始化返回数组，其长度与输入数组temperatures相同
        // 用于存储每个温度日后第一个更高温度的天数
        int ret[] = new int[temperatures.length];
        
        // 使用双端队列（Deque）来维护一个单调递减栈
        Deque deque = new ArrayDeque<>();

        // 遍历每个温度
        for(int i = 0 ; i < temperatures.length; i++){
            // 当队列不为空且当前温度大于队列头部的温度时
            while(!deque.isEmpty() && temperatures[i] > temperatures[deque.getFirst()]){
                // 计算当前温度与之前温度的天数差，并存储在返回数组中
                ret[deque.getFirst()] = i - deque.getFirst();
                // 从队列中移除之前的索引
                deque.removeFirst();
            }
            // 将当前索引压入队列头部
            deque.addFirst(i);
        }

        // 返回结果数组
        return ret;
    }
}

下一个更大元素 I

496. 下一个更大元素 I - 力扣（LeetCode）

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 使用哈希表来存储nums1中的元素及其索引
        Map hashmap = new HashMap<>();
        for(int i = 0 ; i < nums1.length; i++){
            hashmap.put(nums1[i], i);
        }

        // 初始化返回数组，其长度与nums1相同
        int ret[] = new int[nums1.length];
        // 使用双端队列来维护一个单调递减栈
        Deque deque = new ArrayDeque<>();
        // 将返回数组填充为-1，表示没有下一个更大元素
        Arrays.fill(ret, -1);

        // 遍历nums2中的每个元素
        for(int i = 0 ; i < nums2.length; i++){
            // 当队列不为空且当前元素大于队列头部的元素时
            while(!deque.isEmpty() && nums2[i] > nums2[deque.getFirst()]){
                // 从队列中取出栈顶元素
                int key = nums2[deque.removeFirst()];
                // 如果哈希表中包含该元素，则在返回数组中记录下一个更大元素的索引
                if(hashmap.containsKey(key)){
                    ret[hashmap.get(key)] = nums2[i];
                }
            }
            // 将当前索引压入队列头部
            deque.addFirst(i);
        }
        // 返回结果数组
        return ret;
    }
}

下一个更大元素II

503. 下一个更大元素 II - 力扣（LeetCode）

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // 获取数组nums的长度
        int size = nums.length;

        // 使用双端队列来维护一个单调递减栈
        Deque deque = new ArrayDeque<>();
        // 初始化返回数组，其长度与nums相同
        int ret[] = new int[size];
        // 将返回数组填充为-1，表示没有下一个更大元素
        Arrays.fill(ret, -1);

        // 遍历数组nums两次，模拟一个环形数组
        for(int i = 0 ; i < 2 * size; i++){
            // 当队列不为空且当前元素大于队列头部的元素时
            while(!deque.isEmpty() && nums[deque.getFirst()] < nums[i % size]){
                // 队列头部元素的下一个更大元素是当前元素
                ret[deque.getFirst()] = nums[i % size];
                // 从队列中移除栈顶元素
                deque.removeFirst();
            }
            // 将当前索引对nums长度取余，模拟环形数组
            // 将当前索引压入队列头部
            deque.addFirst(i % size);
        }

        // 返回结果数组
        return ret;
    }
}

接雨水

42. 接雨水 - 力扣（LeetCode）

class Solution {
    public int trap(int[] height) {
        // 如果数组长度小于等于2，无法形成积水，返回0
        if(height.length <= 2){
            return 0;
        }

        // 使用双端队列来维护一个单调递增栈
        Deque deque = new ArrayDeque<>();
        // 初始化积水量为0
        int v = 0;

        // 将数组的第一个元素索引0压入队列
        deque.addLast(0);

        // 从数组的第二个元素开始遍历
        for(int i = 1; i < height.length; i++){
            // 如果当前元素的高度小于等于栈顶元素的高度，压入栈中
            if(height[deque.getLast()] >= height[i]){
                deque.addLast(i);
            }else{
                // 如果当前元素的高度大于栈顶元素的高度，弹出栈顶元素直到找到小于当前元素的高度
                while(!deque.isEmpty() && height[deque.getLast()] < height[i]){
                    // 弹出的元素索引存储在midIndex中
                    int midIndex = deque.removeLast();
                    // 如果栈中还有元素，说明找到了积水的边界
                    if(!deque.isEmpty()){
                        // 计算积水的高度，取左右边界高度的最小值减去当前柱子的高度
                        int h = Math.min(height[deque.getLast()], height[i]) - height[midIndex];
                        // 计算积水的宽度，即当前索引与栈顶索引的差值减1
                        int w = i - deque.getLast() - 1;
                        // 累加积水量
                        v += h * w;
                    }
                }
                // 将当前元素的索引压入栈中
                deque.addLast(i);
            }
        }
        // 返回总积水量
        return v;
    }
}

柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 使用双端队列来模拟栈的操作
        Deque deque = new ArrayDeque<>();

        // 创建一个新的数组，将原数组的高度值加上0作为边界
        int localHeights[] = new int[heights.length + 2];
        for(int i = 0 ; i < heights.length; i++){
            localHeights[i + 1] = heights[i];
        }
        // 在数组的两端添加0，以便处理边界情况
        localHeights[0] = 0;
        localHeights[localHeights.length - 1] = 0;

        // 将索引0入栈，作为初始的边界
        deque.addLast(0);

        // 用于记录计算出的最大矩形面积
        int s = 0;

        // 遍历新数组中的每个元素
        for(int i = 1 ; i < localHeights.length; i++){
            // 如果当前元素的高度小于等于栈顶元素的高度，则将当前索引入栈
            if(localHeights[deque.getLast()] <= localHeights[i]){
                deque.addLast(i);
            }else{
                // 如果当前元素的高度大于栈顶元素的高度，则不断弹出栈顶元素
                while(!deque.isEmpty() && localHeights[deque.getLast()] > localHeights[i]){
                    int midIndex = deque.removeLast(); // 弹出栈顶元素的索引
                    if(!deque.isEmpty()){
                        // 计算弹出元素的左边界索引
                        int leftIndex = deque.getLast();
                        // 当前索引作为右边界
                        int right = i;

                        // 计算弹出元素的高度和宽度
                        int h = localHeights[midIndex];
                        int w = right - leftIndex - 1;

                        // 更新最大矩形面积
                        s = Math.max(s, h * w);
                    }
                }
                // 将当前索引入栈
                deque.addLast(i);
            }
        }
        // 返回计算出的最大矩形面积
        return s;
    }
}