503.下一個更大元素II
題目鏈接
力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺
求解思路
重點在如何處理循環數組。
方案一：
直接將兩個數組拼接在一起，然后使用單調棧求下一個最大值。
方案二：
在遍歷的過程中模擬走兩遍nums（詳見代碼）。
代碼
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);if (nums.size() == 0) return result;stack<int> st;st.push(0);for (int i = 1; i < nums.size() * 2; i++){if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size());else{while (!st.empty() && nums[i % nums.size()] > nums[st.top()]){result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}}return result;}
};42. 接雨水
題目鏈接
力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺
求解思路
對于一個元素，尋找它的右邊和左邊的第一個最大元素。
本題的幾個重點：
1.單調棧是按行方向來計算雨水的
2.單調棧的元素順序（從棧頭到棧底）
應該是從小到大的順序。一旦發現添加的柱子高度大于棧頭元素了，此時就出現凹槽了，棧頭元素就是凹槽底部的柱子，棧頭第二個元素就是凹槽左邊的柱子，而添加的元素就是凹槽右邊的柱子。
3.遇到相同高度的柱子的處理
遇到相同的元素，更新棧內下標，就是將棧里元素（舊下標）彈出，將新元素（新下標）加入棧中。
4.棧內保存的數值
存放下標。
單調棧的處理邏輯：
三種情況
1.當前遍歷的元素（柱子）高度小于棧頂元素的高度
把這個元素加入棧中。
2.當前遍歷的元素（柱子）高度等于棧頂元素的高度
更新棧頂元素。
3.當前遍歷的元素（柱子）高度大于棧頂元素的高度
此時出現凹槽。
取棧頂元素，將棧頂元素彈出，這個就是凹槽的底部，也就是中間位置，下標記為mid，對應的高度為height[mid]。
此時的棧頂元素st.top()，就是凹槽的左邊位置，下標為st.top()，對應的高度為height[st.top()]（就是圖中的高度2）。
當前遍歷的元素i，就是凹槽右邊的位置，下標為i，對應的高度為height[i]（就是圖中的高度3）。
雨水高度是（凹槽左邊和右邊高度的較小值）-（凹槽底部高度），雨水寬度是凹槽右邊下標-凹槽左邊下標-1，雨水的體積是高度*寬度。
代碼
class Solution {
public:int trap(vector<int>& height) {if (height.size() <= 2) return 0;stack<int> st;st.push(0);int sum = 0;for (int i = 1; i < height.size(); i++){if (height[i] < height[st.top()]){st.push(i);}else if (height[i] == height[st.top()]){st.pop();st.push(i);}else{while (!st.empty() && height[i] > height[st.top()]){int mid = st.top();st.pop();if (!st.empty()){int h = min(height[st.top()], height[i]) - height[mid];int w = i - st.top() - 1;sum += h * w;}}st.push(i);}}return sum;}
};
)