Day59

下一個(gè)更大元素II

503. 下一個(gè)更大元素 II - 力扣（LeetCode）

題目

給定一個(gè)循環(huán)數(shù)組（最后一個(gè)元素的下一個(gè)元素是數(shù)組的第一個(gè)元素），輸出每個(gè)元素的下一個(gè)更大元素。數(shù)字 x 的下一個(gè)更大的元素是按數(shù)組遍歷順序，這個(gè)數(shù)字之后的第一個(gè)比它更大的數(shù)，這意味著你應(yīng)該循環(huán)地搜索它的下一個(gè)更大的數(shù)。如果不存在，則輸出 -1。

示例 1:

• 輸入: [1,2,1]
• 輸出: [2,-1,2]
• 解釋: 第一個(gè) 1 的下一個(gè)更大的數(shù)是 2；數(shù)字 2 找不到下一個(gè)更大的數(shù)；第二個(gè) 1 的下一個(gè)最大的數(shù)需要循環(huán)搜索，結(jié)果也是 2。

提示:

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

思路

本題要循環(huán)數(shù)組

查找元素右邊最大值，使用單調(diào)遞增棧（從?？诘綏５?#xff09;

代碼

class Solution {public int[] nextGreaterElements(int[] nums) {int len = nums.length;int res[] = new int[len];Arrays.fill(res, -1);LinkedList<Integer> stack = new LinkedList<>();stack.push(0);for(int i = 1; i < len * 2; i++){if(nums[stack.peek() % len] > nums[i % len]) stack.push(i);else if(nums[stack.peek() % len] == nums[i % len]) stack.push(i);else {while(!stack.isEmpty() && nums[stack.peek() % len] < nums[i % len]){res[stack.peek() % len] = nums[i % len];stack.pop();}stack.push(i);}}return res;}
}

接雨水

42. 接雨水 - 力扣（LeetCode）

題目

給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

• 輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
• 輸出：6
• 解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）。

示例 2：

• 輸入：height = [4,2,0,3,2,5]
• 輸出：9

思路

只寫了單調(diào)棧，其他方法（雙指針，動(dòng)態(tài)規(guī)劃）看

代碼隨想錄 (programmercarl.com)

準(zhǔn)備工作

那么本題使用單調(diào)棧有如下幾個(gè)問題：

• 首先單調(diào)棧是按照行方向來計(jì)算雨水
• 使用單調(diào)棧內(nèi)元素的順序

從棧頭（元素從棧頭彈出）到棧底的順序應(yīng)該是從小到大的順序。

因?yàn)橐坏┌l(fā)現(xiàn)添加的柱子高度大于棧頭元素了，此時(shí)就出現(xiàn)凹槽了，棧頭元素就是凹槽底部的柱子，棧頭第二個(gè)元素就是凹槽左邊的柱子，而添加的元素就是凹槽右邊的柱子。

• 遇到相同高度的柱子怎么辦。

遇到相同的元素，更新棧內(nèi)下標(biāo)，就是將棧里元素（舊下標(biāo)）彈出，將新元素（新下標(biāo)）加入棧中。

因?yàn)槲覀円髮挾鹊臅r(shí)候 如果遇到相同高度的柱子，需要使用最右邊的柱子來計(jì)算寬度。

• 棧里要保存什么數(shù)值

使用單調(diào)棧，也是通過 長(zhǎng) * 寬 來計(jì)算雨水面積的。

長(zhǎng)就是通過柱子的高度來計(jì)算，寬是通過柱子之間的下標(biāo)來計(jì)算，

那么棧里有沒有必要存一個(gè)pair<int, int>類型的元素，保存柱子的高度和下標(biāo)呢。

其實(shí)不用，棧里就存放下標(biāo)就行，想要知道對(duì)應(yīng)的高度，通過height[stack.top()] 就知道彈出的下標(biāo)對(duì)應(yīng)的高度了。

單調(diào)棧處理邏輯

以下邏輯主要就是三種情況

• 情況一：當(dāng)前遍歷的元素（柱子）高度小于棧頂元素的高度 height[i] < height[st.top()]
  • 如果當(dāng)前遍歷的元素（柱子）高度小于棧頂元素的高度，就把這個(gè)元素加入棧中，因?yàn)闂＠锉緛砭鸵３謴男〉酱蟮捻樞?#xff08;從棧頭到棧底）。

if(height[i] < height[stack.peek()]) stack.push(i)

• 情況二：當(dāng)前遍歷的元素（柱子）高度等于棧頂元素的高度 height[i] == height[st.top()]
  • 如果當(dāng)前遍歷的元素（柱子）高度等于棧頂元素的高度，要跟更新棧頂元素，因?yàn)橛龅较嘞嗤叨鹊闹?#xff0c;需要使用最右邊的柱子來計(jì)算寬度。

if(height[i] == height[stack.peek()]){stack.pop();stack.push(i);
}

• 情況三：當(dāng)前遍歷的元素（柱子）高度大于棧頂元素的高度 height[i] > height[st.top()]
  • 如果當(dāng)前遍歷的元素（柱子）高度大于棧頂元素的高度，此時(shí)就出現(xiàn)凹槽了

那么雨水高度是 min(凹槽左邊高度, 凹槽右邊高度) - 凹槽底部高度，代碼為：int h = min(height[st.top()], height[i]) - height[mid];

雨水的寬度是 凹槽右邊的下標(biāo) - 凹槽左邊的下標(biāo) - 1（因?yàn)橹磺笾虚g寬度），代碼為：int w = i - st.top() - 1 ;

當(dāng)前凹槽雨水的體積就是：h * w。

while(!stack.isEmpty() && height[i] > height[stack.peek()]){int mid = stack.peek();stack.pop();if(!stack.isEmpty()){int h = Math.min(height[stack.peek()], height[i]) - height[mid];int w = i - stack.peek() - 1; // 注意減一，只求中間寬度sum += w * h;}
}
stack.push(i);

代碼

class Solution {public int trap(int[] height) {if (height.length <= 2) return 0;int sum = 0;LinkedList<Integer> stack = new LinkedList<>();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()]){stack.pop();stack.push(i);}else {while(!stack.isEmpty() && height[i] > height[stack.peek()]){int mid = stack.peek();stack.pop();if(!stack.isEmpty()){int h = Math.min(height[stack.peek()], height[i]) - height[mid];int w = i - stack.peek() - 1; // 注意減一，只求中間寬度sum += w * h;}}stack.push(i);}}return sum;}
}