739.每日温度
题目的背后含义简化为就是找到每一个元素右边比它大的第一个元素的位置，两者位置相减即可得到该元素的结果
问：什么时候需要用到单调栈？
答：通常是一维数组，要寻找一个元素的右边或者左边第一个比自己大或者小的元素的位置。
使用单调栈的注意事项：
1.单调栈存放的元素是什么？
答：单调栈中只需要存放元素的下标i即可，如果需要使用对应的元素，直接T[i]就可以取出
2.单调栈里顺序是递增的？还是递减的？
顺序是指 从栈头到栈尾 的顺序。
这道题我们使用的是递增栈，因为只有递增的时候，栈里要加入一个元素i时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i
总结来说：如果求一个元素右边第一个更大元素，单调栈就是递增的；如果求一个元素右边第一个更小元素，单调栈就是递减的。
使用单调栈主要有三个判断条件
(1)当前遍历的元素T[i]小于栈顶元素T[stack.peek()]
(2)当前遍历的元素T[i]等于栈顶元素T[stack.peek()]
(3)当前遍历的元素T[i]大于栈顶元素T[stack.peek()]
代码实现：
//通过双端队列Deque的实现类ArrayDeque来模拟栈
Deque<Integer> stack = new ArrayDeque<>();
int[] result = new int[T.length];
//先将第一个元素的下标0存入栈中
stack.push(0);
//开始遍历
for(int i = 1; i < T.length; i++){
while(!stack.isEmpty() && T[i] > T[stack.peek()]){
result[stack.peek()] = i – stack.peek();
stack.pop();
}
stack.push(i);
}
return result;
补充知识点：
在JAVA中，可以通过双端队列Deque的实现类ArrayDeque和LinkedList来模拟栈。ArrayDeque用的更多。
Deque<Integer> stack = new ArrayDeque<>();
栈stack提供的方法常用的有：
入栈push()
出栈pop()
查看栈顶元素peek()
判断栈是否为空isEmpty()
获取栈的大小size()
ArrayDeque和LinkedList什么区别？
答：ArrayDeque在大多数情况下性能更优，尤其是在需要频繁进行两端操作且偶尔需要随机访问的场景下。而LinkedList则在需要在任意位置频繁插入和删除元素时更具优势。
496.下一个更大元素I
建立nums1和nums2的映射关系，我们是遍历nums2，找到右边比它大元素时，去看该元素是不是出现在nums1中，然后根据映射关系得到它在nums1中的下标
在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元素的下标来更新result数组。
题目中提到两个没有重复元素的数组，所以可以用map来做映射。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。
栈头到栈底的顺序由小到大递增的。
分析三种情况
(1)当前遍历的元素T[i]小于栈顶元素T[stack.peek()]
满足递增栈，所以直接入栈
(2)当前遍历的元素T[i]等于栈顶元素T[stack.peek()]
也是直接入栈
(3)当前遍历的元素T[i]大于栈顶元素T[stack.peek()]
此时找到右边第一个比自己大的元素，判断栈顶元素是否存在nums1中出现过，因为栈里的元素是nums2的，如果出现过，开始记录结果。记录完结果，出栈，入栈。
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
Map<Integer, Integer> nums1Map = new HashMap<>();
for(int i = 0; i < result.length; i++){
result[i] = -1;
nums1Map.put(nums1[i], i);//key为数值，value为索引下标
}
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);//将第一个元素入栈
for(int i = 1; i < nums2.length; i++){
if(nums2[i] <= nums2[stack.peek()]){//情况1和2合起来了
stack.push(i);//直接入栈
}else{
while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){//情况3
if(nums1Map.containsKey(nums2[stack.peek()])){//判断是否需要记录
int index = nums1Map.get(nums2[stack.peek()]);
result[index] = nums2[i];
}
stack.pop();//出栈
}
stack.push(i);//入栈
}
}
return result;
}
503.下一个更大元素II
与496.下一个更大元素I殊途同归，只不过这道题要处理的是一个循环数组。
解题思路就是：将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集result数组resize到原数组大小就可以了。在此思路上加以改造，不用重新塑造新的拼接数组nums，而是在原来的基础数组nums上模拟遍历两遍。
public int[] nextGreaterElements(int[] nums) {
int[] result = new int[nums.length];
//初始化为-1
for(int i = 0; i < result.length; i++){
result[i] = -1;
}
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
int len = nums.length;
for(int i = 1; i < len * 2; i++){//两倍长度，模拟遍历两边数组
if(nums[i % len] <= nums[stack.peek()]){
stack.push(i % len);
}else{
while(!stack.isEmpty() && nums[i % len] > nums[stack.peek()]){
result[stack.peek()] = nums[i % len];
stack.pop();
}
stack.push(i % len);
}
}
return result;
}
42.接雨水
需要找到一个元素，右边最大元素以及左边最大元素，来计算雨水面积。
1.按照行计算
2.通过 长*宽 来计算雨水面积
3.
情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
直接stack.push(i)
情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
直接stack.push(i)
情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]
先stack.pop()
然后处理逻辑：计算面积就是 栈顶和栈顶的下一个元素以及要入栈的元素 这三个元素计算
左墙是栈顶的下一个元素值，右墙是即将入栈的元素，中间是栈顶元素，
计算面积要先计算长和宽
长=左右墙取最小值 – 凹槽中间底部高度，即int h = Math.min(height[i], height[stack.peek()]) – height[mid];
宽=凹槽右边的下标-凹槽左边的下标-1，即int w = i – stack.peek() – 1;
public int trap(int[] height) {
Deque<Integer> stack = new ArrayDeque<>();
int result = 0;
stack.push(0);
for(int i = 1; i < height.length; i++){
if(height[i] <= height[stack.peek()]){
stack.push(i);
}else{
while(!stack.isEmpty() && height[i] > height[stack.peek()]){
//业务逻辑
int mid = height[stack.pop()];
if(!stack.isEmpty()){
int right = height[i];
int left = height[stack.peek()];
int h = Math.min(left, right) – mid;
int w = i – stack.peek() – 1;
result += h*w;
}
}
//入栈
stack.push(i);
}
}
return result;
}
82. 柱状图中最大的矩形
确定result[i]位置的面积逻辑
i位置的元素，向左找第一个比它小的元素，向右找第一个比它小的元素。这样一来就可以确定宽度，而高度就是它本身（栈顶元素）的高度。
所以这道题的宽度是要计算的。
宽度w = 右边小元素下标 – 左边小元素下标 – 1；
在height数组开头和结尾都加一个元素0，为了避免 height数组 一开始就是单调的，导致不会走情况三。
int[] newHeights = new int[heights.length + 2];
for(int i = 1; i < newHeights.length – 1; i++){
newHeights[i] = heights[i – 1];
}
Deque<Integer> stack = new ArrayDeque<>();
int result = 0;
stack.push(0);
for(int i = 1; i < newHeights.length; i++){
if(newHeights[i] >= newHeights[stack.peek()]){
stack.push(i);
}else{
while(!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]){
int midIndex = stack.pop();
if(!stack.isEmpty()){
int h = newHeights[midIndex];
int w = i – stack.peek() – 1;
result = Math.max(result, h*w);
}
}
stack.push(i);
}
}
return result;
}
小总结
接雨水与柱状图中最大的矩形，这两道题就是要确定单调栈存放的元素是单增的还是单减的。
相同点：
1.计算面积 都是需要三个元素，要插入的元素，栈顶的元素，栈顶的下一个元素
2.遍历数组元素插入单调栈的情况也都是 有三种
不同点：
1.单调栈 存放的元素 顺序不一样 接雨水是单调递增 ， 柱状图矩形面积是单调递减
2.求宽和高逻辑不同 接雨水中要确定 既定元素 右边第一个比它大的元素作为右高墙， 左边第一个比它大的元素作为左高墙，宽是两者相减+1，高是 左右墙取最小减去既定元素高度 即为 雨水的高度；
柱状图中 要确定 既定元素 右边第一个比它小的元素，左边第一个比它小的元素，宽是两者相减-1，高就是该既定元素自己的高度。
3.柱状图矩形会有特殊情况，初始给的是默认值就不会走情况三，所以要把数组的头部和尾部都加一个0
所以，接雨水是求的柱形外面的面积，柱形图矩形求的是柱形里面的面积。
No responses yet