代码随想录算法训练营第五十九天 | LeetCode 503. 下一个更大元素 II、42. 接雨水
1. LeetCode 503. 下一个更大元素 II
1.1 思路
- 本题是给一个数组求右边第一个比当前元素大的元素，好像和739. 每日温度差不多，但本题多了个循环数组的要求，首尾是相连的
- 思路 1：建立一个新数组，把原数组扩充一倍再放入这个新数组中，即这个新数组的长度是原数组的 2 倍，然后线性遍历求当前元素右边第一个比其大的元素，这样就不用循环数组了，最后返回一半数组即可。这么写就是空间复杂度就是创建了一个 2 倍的数组，时间复杂度就是 O(n)
- 思路 2：在原数组模拟循环的方式，通过取模的方式。遍历数组时还是通过 2 倍数组来遍历，for（int i=0；i<nums.length*2；i++），如果直接取 i，当超过 nums.length 时就会越界，因此 i=i%nums.length，这样当超出范围时一取模就又回来了。
- 单调栈的模板代码：result 数组存储结果，注意要将数组默认初始化为全-1 的值，因为本题找不到存的是-1，然后定义个栈，把 0 下标先放入 stack.push(0)。for（int i=1；i<nums.length*2；i++）从 1 开始是因为 0 下标已经存入。避免 i 越界，i=i%nums.length；if（nums[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);//默认全部初始化为-1 Stack<Integer> 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];//更新result st.pop();//弹出栈顶 } st.push(i % size); } return result; } }
2. LeetCode 42. 接雨水
2.1 思路
- 本题是给一个 height 数组“接雨水”，因为这些数组的元素形成柱子就会有一些凹槽，就能存些雨水，最后就返回能接多少岁雨水。
- 引出单调栈：单调栈适用于找到左边或者右边第一个比当前元素大的元素。本题的栈是递增还是递减呢？本题中我们不仅要求右边第一个比其大的元素，还要求左边第一个比其大的元素，因为要找到凹槽嘛，而我们确定一个凹槽就是要左右两边的柱子顶起来，中间有个底托起来
- 本题单调栈的工作过程是当前元素和栈顶元素比较，本题中如果当前元素大于栈顶元素那就是右边第一个比其大的元素，此时栈顶元素就是底了，右边的柱子也找到了，就差左边的柱子了，其实就在栈里，就是栈顶的下一个元素，这个就是左边第一个比其大的元素。
- 当前元素和栈顶元素的比较就大于等于小于三种情况。本题中，小于仍然是放入栈中；等于也是放入栈中，也可以把栈顶弹出再将但当前元素放入，其实都可以，但我们选择前者，这两个的区别就是计算有点差异而已；大于时，此时栈顶就是底，当前元素就是右边的柱子，左边的柱子就是栈顶下一个元素。
- 计算过程：底=stack.pop()；柱子的高度要取最小值，因为取高的部分会漏出去，想象一下凹槽存水的原理木桶效应就知道了，h=Math.min（stack.peek()，height[i]），然后 h 减去 底的高度差就是存水的高度，凹槽的宽度就是右柱子的下标减去左柱子的下标，即 w=i-stack.peek()-1，为什么需要减 1，举例右柱子 4 下标，左柱子 2 下标，宽度应该是 1，求的就是中间凹槽的宽度，因此要-1。h*w 就是面积。因为栈顶前面弹出了，当前元素仍有可能比栈顶大，因此还能确定凹槽，因此用 while 循环遍历。前面说等于时是把当前元素直接放入还是先弹出再放入当前元素的时候，说的是都可以是因为，如果放入此时的最矮柱子和底的高度差是 0，面积也是 0，而如果弹出再放入就是少算了这个 0，因此没区别。
- 单调栈求面积是横向求的，而暴力是纵向求的。
- 代码实现：定义 sum 存面积，定义栈然后放入 0 下标，for（int i=1；i<height.length；i++）从 1 开始是因为 0 下标已经放入。if（height[i]<=height[stack.peek()]）stack.push(i)；else while（!stack.empty()&&heigth[i]>height[stack.peek()]）int middle=stack.pop()这是底，if（!stack.empty()）这里要判断一下不能为空栈，h=Math.min（height[stack.peek()]，height[i]）-height[mid] 这是高度差，w=i-stack.peek()-1 这是宽度；sum+=h*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 height Stack<Integer> stack = new Stack<Integer>(); 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当前的index stack.pop(); stack.push(index); }else{ //pop up all lower value int 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; } }
