代码随想录算法第四十九天| LeetCode42接雨水、LeetCode84柱状图中最大的矩形

LeetCode 42 接雨水题目链接42.接雨水文档讲解代码随想录视频讲解接雨水思路与感想接雨水这道题目可以说是家喻户晓了我在还没有系统性学习算法题的时候就已经知道了这么一则津津乐道的故事字节里面的保洁阿姨都会接雨水。轮到我来解这道题目的时候真的是眉头紧锁不知道从何下手。后面复盘当时的思路受阻的一大原因就是没有想要使用两层for循环暴力求解但目光却局限在水量取决于左右两个柱子较矮的那个根本没想清楚自己是纵向求解还是横向求解。现在把四种解法都理解后再来写感想发现自己完全就像无头苍蝇。先说暴力解法核心思路是遍历除了第一个和最后一个柱子考虑每个柱子处纵向可能积累的雨水量两层for循环外层遍历所有柱子内层通过两个从i向外的for循环得到当前遍历柱子的左右柱子的最大高度并且取较小的那个决定当前柱子处能积累的雨水量。接着是双指针解法这是基于刚刚暴力解法的优化版本因为暴力解法也可以看作一种双指针暴力解法在内层两个for循环求左右柱子最大高度的时候是有进行重复遍历和计算的别忘了我们外层还有个遍历所有柱子的for循环这样一来代码的冗余计算肉眼可见。而第二种双指针解法则是要避免这种重复它是构造了两个数组maxLeft和maxRight记录第i个柱子左边和右边最高柱子的高度用两个for循环进行填值处理逻辑就是不断求最大值即可一个正序求一个倒序求。最后再用一个for循环进行暴力解法外层for循环的操作遍历所有柱子求每个柱子可鞥存储的最大雨水量这样一来时间复杂度就由On2变为On了。第三种方法是双指针优化的方法可以看到原来的双指针方法是用来maxLeft和maxRight两个数组来存储其实这两个数组办到的事可以用两个变量完成还是用maxLeft和maxRight表示他们的含义也是左侧和右侧最高柱子的高度。只不过我们还需要两个指针left和right来遍历所有的柱子为了实现与数组相同的效果maxLeft和maxRight需要实时更新。这个解法的核心逻辑就是哪边高度限制更低就先结算哪边指针处的雨水量并更新这一边的指针即向内移动。这样空间上就优化为O1了。以上三种方法都是每个柱子从左往右纵向求它可能存储的最大雨水量接下来的第四种单调栈方法是属于从下往上横向求值这个不只是要记录雨水高度还要记录宽度。刚看到这个方法的时候我还以为是接雨水改题了哪来的宽度后面才晓得是因为单调栈方法的特性。这里因为求得雨水其实就是在一个凹槽中左侧柱子高度大于中柱高度形成单调递增栈用递增栈本质上求的是右边第一个高于中柱单调栈解法的思路是遍历所有柱子然后比较当前遍历的柱子高度与栈顶柱子高度如果说小于的话那就直接push进去等于得话可以选择push但会导致后面else逻辑多一次水量为0得无意义计算所以可以先poll掉栈顶元素然后再push进去大于的话就说明找到了右侧柱子了此时栈顶就是中柱子取到中柱子值顺便把它poll掉方便取左侧柱子的值之后求高度就跟上面三种解法一样然后还有求宽度宽度等于right - left - 1表示水宽然后水量总体就求出来了。收获1.接雨水的纵向和横向求值之间的区别2.双指针与单调栈思路// 暴力解法 class Solution { public int trap(int[] height) { int result 0; // 记录雨水总和 for (int i 0; i height.length; i) { // 遍历每个柱子可能存储的雨水量 if (i 0 || i height.length - 1) { // 第一个和最后一个柱子不能存储雨水 continue; } int rheight height[i]; // rheight表示当前柱子i右边最高柱子的高度 int lheight height[i]; // 同上初始化的目的是为了让边界合理化 for (int right i 1; right height.length; right) { // 从位置i向右遍历 if (height[right] rheight) { // 不断更新rheight rheight height[right]; // 保证rheight为i右侧最高柱子的高度 } } for (int left i - 1; left 0; left--) { // 同上 if (height[left] lheight) { lheight height[left]; } } int h Math.min(lheight,rheight) - height[i]; // i柱子能存储的雨水取决于lheight和rheight两者的最小值再减去i柱子本身的高度 if (h 0) { result h; } } return result; } }// 双指针 class Solution { public int trap(int[] height) { int size height.length; int[] maxLeft new int[size]; // 记录每个柱左边最高柱子的高度(包含自己) int[] maxRight new int[size]; // 记录每个柱右边最高柱子的高度(包含自己) maxLeft[0] height[0]; // 让边界合法化 for (int i 1; i size; i) { maxLeft[i] Math.max(maxLeft[i - 1],height[i]); // 之前的最高与自己高度取最大值 } maxRight[size - 1] height[size - 1]; // 同上 for (int i size - 2; i 0; i--) { maxRight[i] Math.max(maxRight[i 1],height[i]); // 同上 } int result 0; // 记录雨水总量 for (int i 0; i size; i) { int h Math.min(maxLeft[i],maxRight[i]) - height[i]; // 左边最高与右边最高求最小值这个值肯定大于等于0因为求maxLeft和maxRight的时候把height[i]拉进Math.max的式子中了 if (h 0) { result h; } } return result; } }// 双指针优化 class Solution { public int trap(int[] height) { if (height.length 2) { // 柱子的数量小于等于2根本无法聚集雨水剪枝掉即可 return 0; } int maxLeft height[0]; // 记录left左侧最高柱子的高度 int maxRight height[height.length - 1]; // 同上 int left 1; // 左指针 int right height.length - 2; // 右指针 int result 0; // 记录雨水总量 while (left right) { // 两个指针向里靠拢遍历所有柱子 maxLeft Math.max(maxLeft,height[left]); // 每次进入循环不知道哪个指针移动了索性就都更新最高高度 maxRight Math.max(maxRight,height[right]); if (maxLeft maxRight) { // 如果左边最高高度更小那就说明左指针柱子的雨水高度被maxLeft限制死了就先结算left此时柱子处的雨水然后左指针右移 result (maxLeft - height[left]); // 累计雨水 } else { // 同上 result (maxRight - height[right--]); } } return result; } }// 单调栈 class Solution { public int trap(int[] height) { DequeInteger stack new ArrayDeque(); // 递增单调栈本质上找某个元素右边第一个比它更大的元素本题中其实就是在找某个柱子右边第一个比它高的柱子形成凹槽 int result 0; // 记录雨水总量 stack.push(0); // 开启单调栈 for (int i 1; i height.length; i) { // 从第二个柱子开始遍历 if (height[i] height[stack.peek()]) { // 如果当前遍历柱子高度小于栈顶柱子高度直接添入栈中形成递增栈 stack.push(i); } else if (height[i] height[stack.peek()]) { // 如果高度相等就先把栈顶那个与当前遍历柱子高度相同的柱子给poll出栈再把当前遍历的柱子push进来可以让后续的else逻辑中少一次h为0的无意义计算 stack.poll(); stack.push(i); } else { // 发现遍历的柱子高度大于栈顶柱子高度了说明发现了右侧柱 while (!stack.isEmpty() height[i] height[stack.peek()]) { // 循环进行雨水处理操作 int mid stack.poll(); // 此时栈顶柱子就是中间柱先取出来方便后续取到左侧柱 if (!stack.isEmpty()) { // 由于进行了poll操作需要再此保证栈不为空才能进行后续的peek取左侧柱操作 int right i; // 右侧柱下标 int left stack.peek(); // 左侧柱下标 int h Math.min(height[right],height[left]) - height[mid]; // 取决于左侧柱和右侧柱最低的高度再减去中间柱的高度 int w right - left - 1; // 求所求雨水的宽度 result w * h; // 横向求解从下往上 } } stack.push(i); // 同上面逻辑push进去即可 } } return result; } }LeetCode 84 柱状图中最大的矩形题目链接84.柱状图中最大的矩形文档讲解代码随想录视频讲解柱状图中最大的矩形思路与感想这道题简直就是接雨水的孪生兄弟有种既生瑜何生亮的感觉。本题与接雨水的差别在于接雨水求的是柱形外面因为是凹槽而本题求的是柱形内部面积。接雨水中有三个关键变量leftmidright。本题也是一样的首先是mid它是作为基准的柱子下标矩形高度以它为准leftright就是mid左右侧第一个比mid高度低的柱子只要旁边柱子高度比mid高以mid高度为基准的矩形就能一直横向贯穿。所以本题本质上是倒过来求某个元素左右两侧第一个更小的元素上一题接雨水的暴力解法和双指针其实用在本题上也可以行得通另外单调栈解法中则需要使用到递减栈同时还有个区别就是单调栈遍历的数组需要在首尾添0因为如果案例数组为单调的那就会出现只入栈不计算而首尾的0就相当于计算触发器。收获1.单调递减栈的使用注意事项// 单调栈 class Solution { public int largestRectangleArea(int[] heights) { int result 0; int[] newHeights new int[heights.length 2]; for (int i 0; i heights.length; i) { newHeights[i 1] heights[i]; } // 首尾添0防止当案例单调时出现不计算的情况用来当作打破单调的计算触发器 DequeInteger stack new ArrayDeque(); stack.push(0); for (int i 1; i newHeights.length; i) { if (newHeights[i] newHeights[stack.peek()]) { // 本质上求右边第一个小于某柱子高度的柱子所以采用单调递减栈 stack.push(i); } else if (newHeights[i] newHeights[stack.peek()]) { stack.poll(); stack.push(i); } else { while (!stack.isEmpty() newHeights[i] newHeights[stack.peek()]) { int mid stack.peek(); // mid就是那个某柱子同时它也是作为高度基准的柱子 stack.poll(); if (!stack.isEmpty()) { int right i; // right就是mid右侧第一个比它矮的柱子 int left stack.peek(); // left就是mid左侧第一个比它矮的柱子 int h newHeights[mid]; // mid的高度就是基准 int w right - left - 1; // 内部宽度 result Math.max(result,w * h); // 更新最大值 } } stack.push(i); } } return result; } }今天花了大概五个半小时左右做了两道hard题目接雨水解法挺多不过接雨水搞完了后面一题其实理解起来就简单多了本质都是一样的。这周白天都是集中四节数据采集实验课真是累人感觉收获很小基本上都是在照着实验书敲代码跑不通就问AI让AI改。还是再忍忍把只剩下两次实验课了最恼人的是感觉应该写的很快才对可是因为自己对爬虫实在不了解对AI生成的破代码也不知道怎么修改所以一直跑不通有这时间不如赶赶后端进度背背八股原以为是个很好的期末复习机会谁知道一直在改AI的破代码哪来时间复习呀。今天下午和晚上又各有两节选修课都是最后一节了晚上那节期末考这考试也挺逗的明明能用AI四五分钟就能搞定的事情老师还把期末考分成两部分第二部分硬是要开考三十分钟之后才解锁所以只能第二节课再回寝室写题了。中午因为一直在看接雨水加上早八实验课所以下午选修课基本上第一节课很困一直在睡觉第二节课把接雨水暴力解法写了下然后下课健身去了感觉状态不是很好加上平板卧推放在最后练就只推70公斤还差点被压了最近减脂力量好像有点下降了。称了体重现在70公斤两个月减了5公斤还是要管住嘴才行还是那句话纯粹以消耗为目的的有氧不如少吃两口。