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

学习目标：

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

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

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;
    }
}

学习时间：

• 上午两个半小时，整理文档半小时。