网站建设 文库,湛江专业雷剧视频,wordpress页面样式,会员卡怎么制作代码随想录算法训练营第五十九天 | LeetCode 503. 下一个更大元素 II、42. 接雨水 文章链接#xff1a;下一个更大元素 II、接雨水 视频链接#xff1a;下一个更大元素 II、接雨水 1. LeetCode 503. 下一个更大元素 II
1.1 思路
本题是给一个数组求右边第一个比当前元素大的…代码随想录算法训练营第五十九天 | LeetCode 503. 下一个更大元素 II、42. 接雨水 文章链接下一个更大元素 II、接雨水 视频链接下一个更大元素 II、接雨水 1. LeetCode 503. 下一个更大元素 II
1.1 思路
本题是给一个数组求右边第一个比当前元素大的元素好像和739. 每日温度差不多但本题多了个循环数组的要求首尾是相连的思路 1建立一个新数组把原数组扩充一倍再放入这个新数组中即这个新数组的长度是原数组的 2 倍然后线性遍历求当前元素右边第一个比其大的元素这样就不用循环数组了最后返回一半数组即可。这么写就是空间复杂度就是创建了一个 2 倍的数组时间复杂度就是 O(n)思路 2在原数组模拟循环的方式通过取模的方式。遍历数组时还是通过 2 倍数组来遍历forint i0inums.length*2i如果直接取 i当超过 nums.length 时就会越界因此 ii%nums.length这样当超出范围时一取模就又回来了。单调栈的模板代码result 数组存储结果注意要将数组默认初始化为全-1 的值因为本题找不到存的是-1然后定义个栈把 0 下标先放入 stack.push(0)。forint i1inums.length*2i从 1 开始是因为 0 下标已经存入。避免 i 越界ii%nums.lengthifnums[i]nums[stack.peek()]stack.push(i)else while!stack.empty()nums[i]nums[stack.peek()]result[stack.peek()]nums[i]stack.pop()while 循环结束后 stack.push(i)。最终 return result。
1.2 代码
class Solution {public int[] nextGreaterElements(int[] nums) {//边界判断if(nums null || nums.length 1) {return new int[]{-1};}int size nums.length;int[] result new int[size];//存放结果Arrays.fill(result,-1);//默认全部初始化为-1StackInteger st new Stack();//栈中存放的是nums中的元素下标for(int i 0; i 2*size; i) {while(!st.empty() nums[i % size] nums[st.peek()]) {result[st.peek()] nums[i % size];//更新resultst.pop();//弹出栈顶}st.push(i % size);}return result;}
}2. LeetCode 42. 接雨水
2.1 思路
本题是给一个 height 数组“接雨水”因为这些数组的元素形成柱子就会有一些凹槽就能存些雨水最后就返回能接多少岁雨水。引出单调栈单调栈适用于找到左边或者右边第一个比当前元素大的元素。本题的栈是递增还是递减呢本题中我们不仅要求右边第一个比其大的元素还要求左边第一个比其大的元素因为要找到凹槽嘛而我们确定一个凹槽就是要左右两边的柱子顶起来中间有个底托起来本题单调栈的工作过程是当前元素和栈顶元素比较本题中如果当前元素大于栈顶元素那就是右边第一个比其大的元素此时栈顶元素就是底了右边的柱子也找到了就差左边的柱子了其实就在栈里就是栈顶的下一个元素这个就是左边第一个比其大的元素。当前元素和栈顶元素的比较就大于等于小于三种情况。本题中小于仍然是放入栈中等于也是放入栈中也可以把栈顶弹出再将但当前元素放入其实都可以但我们选择前者这两个的区别就是计算有点差异而已大于时此时栈顶就是底当前元素就是右边的柱子左边的柱子就是栈顶下一个元素。计算过程底stack.pop()柱子的高度要取最小值因为取高的部分会漏出去想象一下凹槽存水的原理木桶效应就知道了hMath.minstack.peek()height[i]然后 h 减去 底的高度差就是存水的高度凹槽的宽度就是右柱子的下标减去左柱子的下标即 wi-stack.peek()-1为什么需要减 1举例右柱子 4 下标左柱子 2 下标宽度应该是 1求的就是中间凹槽的宽度因此要-1。h*w 就是面积。因为栈顶前面弹出了当前元素仍有可能比栈顶大因此还能确定凹槽因此用 while 循环遍历。前面说等于时是把当前元素直接放入还是先弹出再放入当前元素的时候说的是都可以是因为如果放入此时的最矮柱子和底的高度差是 0面积也是 0而如果弹出再放入就是少算了这个 0因此没区别。单调栈求面积是横向求的而暴力是纵向求的。代码实现定义 sum 存面积定义栈然后放入 0 下标forint i1iheight.lengthi从 1 开始是因为 0 下标已经放入。ifheight[i]height[stack.peek()]stack.push(i)else while!stack.empty()heigth[i]height[stack.peek()]int middlestack.pop()这是底if!stack.empty()这里要判断一下不能为空栈hMath.minheight[stack.peek()]height[i]-height[mid] 这是高度差wi-stack.peek()-1 这是宽度sumh*w。当 while 循环结束了也把当前元素放入栈中。最终 return sum。
2.2 代码
class Solution {public int trap(int[] height){int size height.length;if (size 2) return 0;// in the stack, we push the index of array// using height[] to access the real heightStackInteger stack new StackInteger();stack.push(0);int sum 0;for (int index 1; index size; index){int stackTop stack.peek();if (height[index] height[stackTop]){stack.push(index);}else if (height[index] height[stackTop]){// 因为相等的相邻墙左边一个是不可能存放雨水的所以pop左边的index, push当前的indexstack.pop();stack.push(index);}else{//pop up all lower valueint heightAtIdx height[index];while (!stack.isEmpty() (heightAtIdx height[stackTop])){int mid stack.pop();if (!stack.isEmpty()){int left stack.peek();int h Math.min(height[left], height[index]) - height[mid];int w index - left - 1;int hold h * w;if (hold 0) sum hold;stackTop stack.peek();}}stack.push(index);}}return sum;}
}
