代码随想录算法训练营第五十九天 _ 单调栈_42. 接雨水、84.柱状图中最大的矩形。

发布时间:2023年12月21日

学习目标:

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

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

60天训练营打卡计划!

学习内容:

42. 接雨水

  • 单调栈作用:记录遍历过且没有被计算的元素下标
  • 单调栈顺序:升序(栈底大)
  • 场景:
    ① height[i] > height[st.peek()] — while循环 — 栈顶元素左右两侧的第一个比他大的元素分别是 height[i]栈内的下一个元素
    int base_position = stk.pop();
    if(!stk.empty()){
    w = i - stk.peek() - 1;
    h = Math.min(height[i], height[stk.peek()]) - height[base_position];
    res += w * h;
    }
    ② height[i] <= height[st.peek()] — 构造出了上升栈
    st.push(i)
class Solution {
    public int trap(int[] height) {
        int res = 0;
        // 高度
        int h = 0;
        // 宽度
        int w = 0;

        // 构造递增的单调栈
        Stack<Integer> stk = new Stack<>();
        stk.push(0);

        for(int i = 1; i < height.length; i++){
            if(height[i] <= height[stk.peek()])  stk.push(i);
            else{
                while(!stk.empty() && height[i] > height[stk.peek()]){
                    int base_position = stk.pop();
                    if(!stk.empty()){
                        w = i - stk.peek() - 1;
                        h = Math.min(height[i], height[stk.peek()]) - height[base_position];
                        res += w * h;
                    }
                }
                stk.push(i);
            }
        }
        return res;
    }
}

84.柱状图中最大的矩形

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

  • 单调栈顺序:降序(栈底小)

  • 特别要求: 需要在首尾元素前后各增加0

  • 场景:
    ① heights[i] > heights[st.peek()] — while循环 — 栈顶元素左右两侧的第一个比他小的元素分别是 heights[i]栈内的下一个元素
    int base = stk.pop();
    if(!stk.empty()){
    res = Math.max(res, h[base] * (i - stk.peek() - 1));
    }
    ② heights[i] <= heights[st.peek()] — 构造出了下降栈
    st.push(i)

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] h = new int[heights.length+2];
        // 补0,防止死循环或者空栈错误
        for(int i = 1; i < heights.length+1; i++){
            h[i] = heights[i-1];
        }

        int res = 0;
        // 降序,要找下一个比他小的,栈底小
        Stack<Integer> stk = new Stack<>();
        stk.push(0);

        for(int i = 1; i < h.length; i++){
            if(h[i] >= h[stk.peek()])  stk.push(i);
            else{
                while(!stk.empty() && h[i] < h[stk.peek()]){
                    int base = stk.pop();
                    if(!stk.empty()){
                        // 此处求最大包含面积时候,
                        // 左右两次第一次比他小的位置只作为限制范围,
                        // 不计入真实面积的计算范围
                        res = Math.max(res, h[base] * (i - stk.peek() - 1));
                    }
                }
                stk.push(i);
            }
        }
        return res;
    }
}

学习时间:

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