代码随想录算法训练营第五十八天 _ 单调栈_155. 最小栈、739.每日温度、496. 下一个更大元素 I、503.下一个更大元素II。

发布时间:2023年12月20日

学习目标:

单调栈是一种特殊的栈数据结构,在栈的基础上增加了一些特定的性质。它主要用于解决一类与元素大小和顺序有关的问题。

  • 特点:
    单调递增栈:栈内元素从栈底到栈顶呈递增的顺序。
    单调递减栈:栈内元素从栈底到栈顶呈递减的顺序。
  • 实现步骤和规则:
    遍历数组或列表:单调栈通常是通过遍历数组或列表实现的,根据特定条件入栈或出栈
    维护单调性:根据问题的需求,维护栈内元素的单调性(递增或递减)。
    元素的入栈和出栈:根据当前元素和栈顶元素的比较,决定入栈或出栈的规则。
    入栈规则:当前元素满足单调性条件时,入栈。
    出栈规则:当前元素破坏单调性条件时,栈顶元素出栈,直到满足单调性条件为止,再将当前元素入栈。

60天训练营打卡计划!

学习内容:

155. 最小栈

  • 好像和单调栈没什么关系,但是这个思路值得学习
  • 当栈中的最大或最小值要更新时,在栈中保存前一个最大或最小值。
class MinStack {
    // 正式栈
    Stack<Integer> stk;
    int min;

    public MinStack() {
        stk = new Stack<>();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int val) {
        // 使用栈将前一个最小值保存
        if(min >= val){
            stk.push(min);
            min = val;
        }
        stk.push(val);
    }
    
    public void pop() {
        // 将栈中存的上一次的最小值取出
        if(stk.peek() == min){
            stk.pop();
            min = stk.peek();
        }
        stk.pop();
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int getMin() {
        return min;
    }
}

739.每日温度

  • 单调栈作用:记录遍历过且没有被计算的元素下标
  • 单调栈顺序:升序
  • 场景:
    ① T[i] > T[st.peek()] — while循环
    res[st.peek()] = i - st.peek()
    st.pop()
    ② T[i] <= T[st.peek()] — 构造出了上升栈
    st.push(i)
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        // 上升的单调栈:存的是遍历过的但未处理的元素下标
        Stack<Integer> st = new Stack<>();

        st.push(0);

        for(int i = 1; i < temperatures.length; i++){
            if(st.empty() || temperatures[i] <= temperatures[st.peek()]){
                st.push(i); 
                // System.out.println("*# " + st.peek() + " " + i);
            }   
            else{
                while(!st.empty() && temperatures[i] > temperatures[st.peek()]){
                    // System.out.println("* " + st.peek() + " " + i);
                    res[st.peek()] = i - st.peek();
                    st.pop();
                }
                // 都出站后要将i入栈
                st.push(i);
            }
        }

        return res;
    }
}

496. 下一个更大元素 I

  • 单调栈作用:记录遍历过且没有被计算的元素下标

  • 单调栈顺序:升序

  • 场景:
    ① nums2[i] > nums2[st.peek()] — while循环
    if(nums1数组中含该st.peek())
    res[nums1数组中该st.peek()的位置] = nums2[i]
    st.pop()
    ② nums2[i] < nums2[st.peek()] — 构造出了上升栈(nums2中所有整数 互不相同)
    st.push(i)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 找不到的位置返回-1,所以直接初始化为-1
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);
        // 构造一个map映射nums1的值和位置关系,便于查询
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums1.length; i++){
            map.put(nums1[i],i);
        }
        // 构造一个递增的上升栈,存的是下标
        Stack<Integer> stk = new Stack<>();
        stk.push(0);

        for(int i = 1; i < nums2.length; i++){
            if(nums2[i] < nums2[stk.peek()])  stk.push(i);
            else{
                while(!stk.empty() && nums2[i] > nums2[stk.peek()]){
                    // 当map中可以找到栈顶元素时,生成一个该值对应的下标的结果数组。
                    // 与739每日温度的唯一区别
                    if(map.containsKey(nums2[stk.peek()])){
                        res[map.get(nums2[stk.peek()])] = nums2[i];
                    }
                    stk.pop();
                }
                // 一定要记得将i这个未处理的值加入到栈中,符合单调栈的结构
                stk.push(i);
            }
        }
        return res;
    }
}

503.下一个更大元素II

  • 与739的区别是:该题目的数组是循环的。
  • 所有的成环的数组都可以在遍历时对其取模实现原地循环
for(int i = 1; i < nums.length * 2; i++){
	nums[i%(nums.length)]
}
  • 单调栈作用:记录遍历过且没有被计算的元素下标

  • 单调栈顺序:升序

  • 场景:
    ① nums[i%(nums.length)] > nums[st.peek()] — while循环
    res[st.peek()] = nums[i]
    st.pop()
    ② nums[i%(nums.length)] <= nums[st.peek()] — 构造出了上升栈
    st.push(i%(nums.length))

class Solution {
    public int[] nextGreaterElements(int[] nums) {    
        // 找不到的位置返回-1,所以直接初始化为-1
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        // 构造一个递增的上升栈,存的是下标
        Stack<Integer> stk = new Stack<>();
        stk.push(0);

        for(int i = 1; i < nums.length*2; i++){
            if(nums[i%nums.length] <= nums[stk.peek()])   stk.push(i%nums.length);
            else{
                while(!stk.empty() && nums[i%nums.length] > nums[stk.peek()]){
                    res[stk.peek()] = nums[i%nums.length];
                    stk.pop();
                }
                // 一定要记得将i这个未处理的值加入到栈中,符合单调栈的结构
                stk.push(i%nums.length);
            }
        }
        return res;
    }
}

学习时间:

  • 上午两个半小时,整理文档半小时。
文章来源:https://blog.csdn.net/weixin_46367158/article/details/135086376
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。