代碼隨想錄算法訓(xùn)練營第五十九天 | LeetCode 503. 下一個(gè)更大元素 II、42. 接雨水

文章鏈接：下一個(gè)更大元素 II、接雨水
視頻鏈接：下一個(gè)更大元素 II、接雨水

1. LeetCode 503. 下一個(gè)更大元素 II

1.1 思路

1. 本題是給一個(gè)數(shù)組求右邊第一個(gè)比當(dāng)前元素大的元素，好像和739. 每日溫度差不多，但本題多了個(gè)循環(huán)數(shù)組的要求，首尾是相連的
2. 思路 1：建立一個(gè)新數(shù)組，把原數(shù)組擴(kuò)充一倍再放入這個(gè)新數(shù)組中，即這個(gè)新數(shù)組的長度是原數(shù)組的 2 倍，然后線性遍歷求當(dāng)前元素右邊第一個(gè)比其大的元素，這樣就不用循環(huán)數(shù)組了，最后返回一半數(shù)組即可。這么寫就是空間復(fù)雜度就是創(chuàng)建了一個(gè) 2 倍的數(shù)組，時(shí)間復(fù)雜度就是 O(n)
3. 思路 2：在原數(shù)組模擬循環(huán)的方式，通過取模的方式。遍歷數(shù)組時(shí)還是通過 2 倍數(shù)組來遍歷，for（int i=0；i<nums.length*2；i++），如果直接取 i，當(dāng)超過 nums.length 時(shí)就會(huì)越界，因此 i=i%nums.length，這樣當(dāng)超出范圍時(shí)一取模就又回來了。
4. 單調(diào)棧的模板代碼：result 數(shù)組存儲(chǔ)結(jié)果，注意要將數(shù)組默認(rèn)初始化為全-1 的值，因?yàn)楸绢}找不到存的是-1，然后定義個(gè)棧，把 0 下標(biāo)先放入 stack.push(0)。for（int i=1；i<nums.length*2；i++）從 1 開始是因?yàn)?0 下標(biāo)已經(jīng)存入。避免 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 循環(huán)結(jié)束后 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];//存放結(jié)果Arrays.fill(result,-1);//默認(rèn)全部初始化為-1Stack<Integer> st= new Stack<>();//棧中存放的是nums中的元素下標(biāo)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 思路

1. 本題是給一個(gè) height 數(shù)組“接雨水”，因?yàn)檫@些數(shù)組的元素形成柱子就會(huì)有一些凹槽，就能存些雨水，最后就返回能接多少歲雨水。
2. 引出單調(diào)棧：單調(diào)棧適用于找到左邊或者右邊第一個(gè)比當(dāng)前元素大的元素。本題的棧是遞增還是遞減呢？本題中我們不僅要求右邊第一個(gè)比其大的元素，還要求左邊第一個(gè)比其大的元素，因?yàn)橐业桨疾勐?#xff0c;而我們確定一個(gè)凹槽就是要左右兩邊的柱子頂起來，中間有個(gè)底托起來
3. 本題單調(diào)棧的工作過程是當(dāng)前元素和棧頂元素比較，本題中如果當(dāng)前元素大于棧頂元素那就是右邊第一個(gè)比其大的元素，此時(shí)棧頂元素就是底了，右邊的柱子也找到了，就差左邊的柱子了，其實(shí)就在棧里，就是棧頂?shù)南乱粋€(gè)元素，這個(gè)就是左邊第一個(gè)比其大的元素。
4. 當(dāng)前元素和棧頂元素的比較就大于等于小于三種情況。本題中，小于仍然是放入棧中；等于也是放入棧中，也可以把棧頂彈出再將但當(dāng)前元素放入，其實(shí)都可以，但我們選擇前者，這兩個(gè)的區(qū)別就是計(jì)算有點(diǎn)差異而已；大于時(shí)，此時(shí)棧頂就是底，當(dāng)前元素就是右邊的柱子，左邊的柱子就是棧頂下一個(gè)元素。
5. 計(jì)算過程：底=stack.pop()；柱子的高度要取最小值，因?yàn)槿「叩牟糠謺?huì)漏出去，想象一下凹槽存水的原理木桶效應(yīng)就知道了，h=Math.min（stack.peek()，height[i]），然后 h 減去 底的高度差就是存水的高度，凹槽的寬度就是右柱子的下標(biāo)減去左柱子的下標(biāo)，即 w=i-stack.peek()-1，為什么需要減 1，舉例右柱子 4 下標(biāo)，左柱子 2 下標(biāo)，寬度應(yīng)該是 1，求的就是中間凹槽的寬度，因此要-1。h*w 就是面積。因?yàn)闂ｍ斍懊鎻棾隽?#xff0c;當(dāng)前元素仍有可能比棧頂大，因此還能確定凹槽，因此用 while 循環(huán)遍歷。前面說等于時(shí)是把當(dāng)前元素直接放入還是先彈出再放入當(dāng)前元素的時(shí)候，說的是都可以是因?yàn)?#xff0c;如果放入此時(shí)的最矮柱子和底的高度差是 0，面積也是 0，而如果彈出再放入就是少算了這個(gè) 0，因此沒區(qū)別。
6. 單調(diào)棧求面積是橫向求的，而暴力是縱向求的。
7. 代碼實(shí)現(xiàn)：定義 sum 存面積，定義棧然后放入 0 下標(biāo)，for（int i=1；i<height.length；i++）從 1 開始是因?yàn)?0 下標(biāo)已經(jīng)放入。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。當(dāng) while 循環(huán)結(jié)束了也把當(dāng)前元素放入棧中。最終 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 heightStack<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]){// 因?yàn)橄嗟鹊南噜弶?#xff0c;左邊一個(gè)是不可能存放雨水的，所以pop左邊的index, push當(dāng)前的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;}
}