【每日一题Day274】LC42接雨水 | 单调栈

简介: 【每日一题Day274】LC42接雨水 | 单调栈

接雨水【LC42】[面试常见]

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

按列求贡献:枚举

首先确定按行计算雨水,还是按列确定雨水

  • 按行计算:按列计算:找每个柱子左右两边第一个大于该柱子高度的柱子
    第一列和最后一列不能容纳雨水,其他列可以容纳的雨水量宽度固定为1,高度取决于min(该列左侧最高的柱子,该列右侧最高的柱子)- 该列的高度

  • 代码
class Solution {
    public int trap(int[] height) {
        int res = 0;
        int lens = height.length;
        for (int i = 1; i < lens - 1; i++){
            int maxL = height[i];
            int maxR = height[i];// Math.min(maxL,maxR) - height[i] 一定大于0
            for (int j = 0; j < i; j++){
                maxL = Math.max(maxL,height[j]);
            }
            for (int k = i + 1; k < lens; k++){
                maxR = Math.max(maxR,height[k]);
            }
            res += Math.min(maxL,maxR) - height[i];
        }
        return res;
    }
}
class Solution {
    public int trap(int[] height) {
        int res = 0;
        int lens = height.length;
        for (int i = 1; i < lens - 1; i++){
            int maxL = 0;
            int maxR = 0;// h可能小于0
            for (int j = 0; j < i; j++){
                maxL = Math.max(maxL,height[j]);
            }
            for (int k = i + 1; k < lens; k++){
                maxR = Math.max(maxR,height[k]);
            }
            int h = Math.min(maxL,maxR) - height[i];
            if (h > 0){
                res += h;
            }
        }
        return res;
    }
}

image.png

按列求贡献:动态规划

使用dp数组记录,每列左边柱子的最高高度和右边柱子的最高高度

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int lens = height.length;
        int[] maxL = new int[lens];
        maxL[0] = height[0];
        int[] maxR = new int[lens];
        maxR[lens-1] = height[lens-1];
        for (int i = 1; i < lens; i++){
            maxL[i] = Math.max(maxL[i-1],height[i]);
        }
        for (int i = lens - 2; i >= 0; i--){
            maxR[i] = Math.max(maxR[i+1],height[i]);
        }
        for (int i = 1; i < lens-1; i++){
            res += Math.min(maxL[i],maxR[i]) - height[i];
        }
        return res;
    }
}

image.png

按行求:单调栈

  • 思路
    使用单调递增栈记录,凹槽处的左边高度和右边高度,按行计算雨水体积。当当前高度大于栈顶元素时,计算雨水体积,高度为左右边高度较小值-凹槽高度,宽度为右边下标-左边下标-1


  • 单调栈里元素是递增呢? 还是递减呢?
    递增,注意一下顺序为 从栈头到栈底的顺序
  • 使用单调栈主要有三个判断条件。
  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
    直接把这个元素压入栈
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
  • 入栈或者不入栈,之前元素弹出或者不弹出不影响结果,(因为遇到相同高度的柱子时,需要使用最右边的柱子以及最左边的柱子计算宽度,左边为相同高度柱子时,计算结果为0)
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
    此时出现凹槽,可以容纳雨水,计算雨水容量,再入栈
  • 取栈顶元素,将栈顶元素弹出,下标即为mid,这个位置为凹槽的底部
  • 再取栈顶元素,下标为st.peekFirst(),这个位置为凹槽的左侧
  • 当前遍历元素为凹槽的右边位置,下标为i
  • 雨水高度为min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度
    int h = min(height[st.peekFirst()], height[i]) - height[mid];
  • 雨水宽度为 凹槽右边的下标 - 凹槽左边的下标 - 1
  • int w = i - st.peekFirst() - 1 ;
  • 雨水的体积为h * w
  • 实现
    2023/7/23
class Solution {
    public int trap(int[] height) {
        // 贡献:每个位置能积累的水量为min(左边最大,右边最大)-柱子高度
        // int n = height.length;
        // int[] left = new int[n], right = new int[n];
        // for (int i = 0; i < n - 1; i++){
        //     left[i + 1] = Math.max(left[i], height[i]);
        //     right[n - i - 2] = Math.max(right[n - i - 1], height[n - i - 1]);
        // }
        // int res = 0;
        // for (int i = 0; i < n; i++){
        //     res += Math.max(Math.min(right[i], left[i]) - height[i], 0);
        // }
        // return res;
        // 单调递增栈【栈顶->栈底】:遇到大于栈顶的柱子,弹出计算雨水量;
        Deque<Integer> st = new LinkedList<>();
        int n = height.length, res = 0;
        for (int i = 0; i < n; i++){
            while (!st.isEmpty() && height[st.peekLast()] <= height[i]){
                int mid = st.pollLast();
                if (st.isEmpty()){
                    break;
                }
                int left = st.peekLast();
                int w = i - left - 1;
                int h = Math.min(height[left], height[i]) - height[mid];
                res += w * h;
            }
            st.addLast(i);
        }
        return res;
    }
}

image.png

目录
相关文章
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
1409 77
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
394 0
栈区的非法访问导致的死循环(x64)
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
698 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
465 11
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
505 9
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
729 7
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
719 5
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
568 0

热门文章

最新文章