代码随想录LeetCode | 单调栈问题

前沿：撰写博客的目的是为了再刷时回顾和进一步完善，其次才是以教为学，所以如果有些博客写的较简陋，是为了保持进度不得已而为之，还请大家多多见谅。

预：看到题目后的思路和实现的代码。

见：参考答案展示。

感思：对比答案后的思考，与之前做过的题目是否有关联。

行：

（1）对于没做出来的题目，阅读答案后重新做一遍；

（2）下次做题可以尝试改善的方向；

（3）有助于理解的相关的题目

优先级：做题进度＞学习&总结＞默写回顾＞做题数量

题目回顾

1.739. 每日温度

题目链接：739. 每日温度

思路

二刷：有使用单调栈的思路，但实现时发现小于等于时不会比较，若一个个比较排序则很低效。

• 当时想错了，小于等于时直接放进去即可，这样放进去肯定是栈顶到栈底从小到大的顺序。

因为是只需要获取大于当前元素的下一个下标与当前下标的位置差，所以栈只需存储下标值。

当前遍历到的值>栈顶下标对应值时，则表示栈顶下标对应值遇到了比它大的下一个最大值。

• 此时将通过临时变量i存储栈顶下标。
  • j-i+1：表示比它大的下一个最大值位置差。
• 并且要考虑栈内其他元素是否小于当前遍历到的值，所以要使用while循环比较。
  • 要注意给i传送新的栈顶下标值，才能更新比较变量。

而小于等于的情况，上面提到了，只需要直接放进去即可。

class Solution {public int[] dailyTemperatures(int[] temperatures) {// 寻找下一个大于值Deque<Integer> deque = new LinkedList();int len = temperatures.length;int[] result = new int[len];deque.push(0);for(int j = 1;j < len;j++){int i = deque.peek();//System.out.println(i);while(!deque.isEmpty() && temperatures[i] < temperatures[j]){deque.pop();result[i] = j-i;if(!deque.isEmpty()){i = deque.peek();}else{deque.push(j);break;}}if(temperatures[i] >= temperatures[j]){deque.push(j);              }}return result;}
}

2.496. 下一个更大元素 I

题目链接：496. 下一个更大元素 I

思路

数组内无重复→哈西搜索勉强实现

相等于从739. 每日温度单个数组比较变成两个数组，但本质相同，直接遍历比较父集

出现更大的值时，则通过哈希搜索子集对应的数组位置，将该更大值赋值给子集对应的数组位置。

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {//找到nums2与nums1匹配的元素，其次计算在nums2右边比它大的值，并且nums1是nums2的子集。Map<Integer,Integer> map = new HashMap<>();int len1 = nums1.length;int len2 = nums2.length;for(int i = 0;i < len1;i++){map.put(nums1[i],i);}int[] result = new int[len1];Arrays.fill(result,-1);Deque<Integer> deque = new LinkedList();deque.push(nums2[0]);for(int i = 1;i < len2;i++){int value = deque.peek();while(!deque.isEmpty() && value < nums2[i]){if(map.containsKey(value)){result[map.get(value)] = nums2[i];}deque.pop();if(!deque.isEmpty()){value = deque.peek();}}deque.push(nums2[i]);}return result;}
}

3.503. 下一个更大元素 II

题目链接：503. 下一个更大元素 II

4. 42. 接雨水

题目链接：42. 接雨水

5.84. 柱状图中最大的矩形

题目链接：84. 柱状图中最大的矩形

总结