下一个更大元素||
503. 下一个更大元素 II - 力扣（LeetCode）
和每日温度一样的套路，就是这里可以循环数组，两个数组拼接，然后循环两遍就行。
public class Solution {public int[] NextGreaterElements(int[] nums) {int leng = nums.Length;int[] result = new int[leng];for(int i=0;i<result.Length;i++)result[i] = -1;if (leng == 0) return result;Stack<int> st = new Stack<int>();st.Push(0);for (int i = 1; i < leng * 2; i++) {if (nums[i % leng] < nums[st.Peek()]) st.Push(i % leng);else if (nums[i % leng] == nums[st.Peek()]) st.Push(i % leng);else {while (st.Count > 0 && nums[i % leng] > nums[st.Peek()]) {result[st.Peek()] = nums[i % leng];st.Pop();}st.Push(i % leng);}}return result;}
}接雨水
42. 接雨水 - 力扣（LeetCode）
双指针法，例如i=4，然后从i开始向左右遍历直到找到左右的最高点，再找到左右的最小值减去i的高得到多少个容纳单位。
单调栈，也和每日温度一样三种情况，如果数组[i]的元素和栈头相同，得先弹出栈内元素再压入，因为最后求最高值是相同元素取最右边的元素，左边用不到；如果大于，取栈头做mid，然后取左右两遍的最小值做高，宽度是i-栈头（不是mid，mid已经弹出）-1，最后相乘就是容积。
双指针
public class Solution {public int Trap(int[] height) {int sum = 0;for(int i=0;i<height.Length;i++){if(i==0 || i==height.Length-1)continue;int lheight = height[i];int rheight = height[i];for(int l=i-1;l>=0;l--){if(lheight < height[l]) lheight=height[l];}for(int r=i+1;i<height.Length;r++){if(rheight < height[i]) rheight=height[r];}int h = Math.Min(lheight,rheight) - height[i];if(h>0)sum+=h;}return sum;}
}单调栈
public class Solution {public int Trap(int[] height) {Stack<int> stack = new Stack<int>();int sum = 0;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.Count > 0 && height[i]>height[stack.Peek()]){int mid = stack.Pop();if(stack.Count > 0){int h = Math.Min(height[stack.Peek()],height[i])-height[mid];int w = i-stack.Peek()-1;sum+= h*w;}}stack.Push(i);}}return sum;}
}柱状图中最大的矩形
84. 柱状图中最大的矩形 - 力扣（LeetCode）
这题主要得注意数组前后都要加上0，如果没加上0，数组元素循环到栈内会一直跳过情况三，具体看代码随想录。
public class Solution {public int LargestRectangleArea(int[] heights) {Stack<int> stack = new Stack<int>();int sum = 0;stack.Push(0);int[] newheights = new int[heights.Length+2];Array.Copy(heights,0,newheights,1,heights.Length);newheights[0] = 0;newheights[newheights.Length-1] = 0;for(int i=1;i<newheights.Length;i++){if(newheights[i] > newheights[stack.Peek()]){stack.Push(i);}else if(newheights[i] == newheights[stack.Peek()]){stack.Pop();stack.Push(i);}else{while(stack.Count > 0 && newheights[i] < newheights[stack.Peek()]){int mid = stack.Pop();if(stack.Count > 0){int left = stack.Peek();int right = i;int w = right-left-1;int h = newheights[mid];sum = Math.Max(sum,h*w);}}stack.Push(i);}}return sum;}
}
