?📝個(gè)人主頁(yè)：@Sherry的成長(zhǎng)之路
🏠學(xué)習(xí)社區(qū)：Sherry的成長(zhǎng)之路（個(gè)人社區(qū)）
📖專欄鏈接：練題
🎯長(zhǎng)路漫漫浩浩，萬(wàn)事皆有期待

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

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

給定一個(gè)循環(huán)數(shù)組 nums （ nums[nums.length - 1] 的下一個(gè)元素是 nums[0] ），返回 nums 中每個(gè)元素的 下一個(gè)更大元素 。

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

在遍歷的過(guò)程中模擬走了兩邊nums。

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

接雨水

42. 接雨水 - 力扣（LeetCode）

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

單調(diào)棧思路

1.首先單調(diào)棧是按照行方向來(lái)計(jì)算雨水，如圖：

在這種情況下，可以接6個(gè)單位的雨水

2.使用單調(diào)棧內(nèi)元素的順序

從大到小還是從小到大呢？

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

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

如圖：

3.遇到相同高度的柱子怎么辦。
遇到相同的元素，更新棧內(nèi)下標(biāo)，就是將棧里元素（舊下標(biāo)）彈出，將新元素（新下標(biāo)）加入棧中。

例如 5 5 1 3 這種情況。如果添加第二個(gè)5的時(shí)候就應(yīng)該將第一個(gè)5的下標(biāo)彈出，把第二個(gè)5添加到棧中。

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

如圖所示：

4.棧里要保存什么數(shù)值
使用單調(diào)棧，也是通過(guò) 長(zhǎng) * 寬 來(lái)計(jì)算雨水面積的。

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

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

Deque<Integer> stack = new LinkedList<>(); // 存著下標(biāo)，計(jì)算的時(shí)候用下標(biāo)對(duì)應(yīng)的柱子高度

明確了如上幾點(diǎn)，我們?cè)賮?lái)看處理邏輯。

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

情況一：當(dāng)前遍歷的元素（柱子）高度小于棧頂元素的高度 height[i] < height[st.top()]
情況二：當(dāng)前遍歷的元素（柱子）高度等于棧頂元素的高度 height[i] == height[st.top()]
情況三：當(dāng)前遍歷的元素（柱子）高度大于棧頂元素的高度 height[i] > height[st.top()]

先將下標(biāo)0的柱子加入到棧中，st.push(0);。 棧中存放我們遍歷過(guò)的元素，所以先將下標(biāo)0加進(jìn)來(lái)。

然后開(kāi)始從下標(biāo)1開(kāi)始遍歷所有的柱子，for (int i = 1; i < height.size(); i++)。

如果當(dāng)前遍歷的元素（柱子）高度小于棧頂元素的高度，就把這個(gè)元素加入棧中，因?yàn)闂＠锉緛?lái)就要保持從小到大的順序（從棧頭到棧底）。

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

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

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

如果當(dāng)前遍歷的元素（柱子）高度大于棧頂元素的高度，此時(shí)就出現(xiàn)凹槽了

取棧頂元素，將棧頂元素彈出，這個(gè)就是凹槽的底部，也就是中間位置，下標(biāo)記為mid，對(duì)應(yīng)的高度為height[mid]（就是圖中的高度1）。

此時(shí)的棧頂元素st.top()，就是凹槽的左邊位置，下標(biāo)為st.top()，對(duì)應(yīng)的高度為height[st.top()]（就是圖中的高度2）。

當(dāng)前遍歷的元素i，就是凹槽右邊的位置，下標(biāo)為i，對(duì)應(yīng)的高度為height[i]（就是圖中的高度3）。

此時(shí)大家應(yīng)該可以發(fā)現(xiàn)其實(shí)就是棧頂和棧頂?shù)南乱粋€(gè)元素以及要入棧的元素，三個(gè)元素來(lái)接水！

那么雨水高度是 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。

class Solution {public int trap(int[] height) {Stack<Integer> st = new Stack<>();st.push(0);int sum = 0;for (int i = 0; i < height.length; i++) {while (!st.isEmpty() && height[i] > height[st.peek()]) {int mid = st.pop();if (!st.isEmpty()) {int h = Math.min(height[st.peek()], height[i]) - height[mid];int w = i - st.peek() - 1;sum += h * w;}}st.push(i);}return sum;}
}

總結(jié)：

今天我們完成了下一個(gè)更大元素II、接雨水兩道題，相關(guān)的思想需要多復(fù)習(xí)回顧。接下來(lái)，我們繼續(xù)進(jìn)行算法練習(xí)。希望我的文章和講解能對(duì)大家的學(xué)習(xí)提供一些幫助。

當(dāng)然，本文仍有許多不足之處，歡迎各位小伙伴們隨時(shí)私信交流、批評(píng)指正！我們下期見(jiàn)~