算法打卡：第十章 单调栈part01

本日劳绩：单调栈理论，逐日温度，下一个更大元素Ⅰ，下一个更大元素Ⅱ

1. 单调栈理论（来自代码随想录）

应用场景：一维数组寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置
存放的元素：数组下标
递增还是递减：单调递增栈（从栈顶到栈底）求右边第一个比自己大的（遍历发现比自己大的元素）；单调递减栈求右边第一个比自己小的（遍历的目的是发现比自己小的元素）
2. 逐日温度

题目链接：739. - 力扣（LeetCode）
思绪：用单调递增栈。如果当前元素比栈顶元素小，直接参加栈；反之记录结果，并不断弹出栈中比当前元素小的元素。
方法：

1. class Solution {
2.     public int[] dailyTemperatures(int[] temperatures) {
3.         int len=temperatures.length;
4.         Stack<Integer> stack=new Stack<>();
5.         int[] result=new int[len];
7.         stack.push(0);
8.         for (int i=1;i<len;i++){
9.             if (temperatures[i]<=temperatures[stack.peek()]){
10.                 stack.push(i);  // 加入更小的元素
11.             }else{
12.                 // 一直弹出比当前元素小的并记录
13.                 while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){
14.                     result[stack.peek()]=i-stack.peek();
15.                     stack.pop();
16.                 }
17.                 stack.push(i);  // 加入当前下标
18.             }
19.         }
21.         return result;
22.     }
23. }

复制代码

3. 下一个更大元素Ⅰ

题目链接：496. - 力扣（LeetCode）
思绪：和逐日温度差不多，只不过在遇到目的元素时，必要判断栈顶元素是否在nums1中。这必要利用map映射存储nums1的值和下标。存储值是为了快速判断当前值是否在nums1中，存储的下标对应结果数组的下标。
方法：

1. class Solution {
2.     public int[] nextGreaterElement(int[] nums1, int[] nums2) {
3.         int len1=nums1.length;
4.         int len2=nums2.length;
6.         int[] result=new int[len1];
7.         Arrays.fill(result,-1);  // 最后栈中留下的元素默认-1
9.         // 记录数组1中值和下标的对应关系，便于判断当前元素是否存在于nums1中，下标对应结果的下标
10.         HashMap<Integer,Integer> map=new HashMap<>();
11.         for (int i=0;i<len1;i++){  
12.             map.put(nums1[i],i);
13.         }
15.         // 求nums2中比当前元素大的右边第一个元素
16.         Stack<Integer> stack=new Stack<>();
17.         stack.push(0);
18.         for (int i=1;i<len2;i++){
19.             if (nums2[i]<=nums2[stack.peek()]){
20.                 stack.push(i);
21.             }else {
22.                 while (!stack.isEmpty()&&nums2[i]>nums2[stack.peek()]){
23.                     if (map.containsKey(nums2[stack.peek()])){  // 收集结果
24.                         int index=map.get(nums2[stack.peek()]);
25.                         result[index]= nums2[i];
26.                     }
27.                     stack.pop();
28.                 }
29.                 stack.push(i);
30.             }
31.         }
33.         return result;
34.     }
35. }

复制代码

总结：Arrays.fill(数组，添补值) 可以用于Java中数组的初始化。
4. 下一个更大元素Ⅱ

题目链接：503. - 力扣（LeetCode）
思绪：遍历两倍长度的数组，求当前元素的值时将下标 i 取余数组长度，其余的思绪和逐日温度雷同。
方法：

1. class Solution {
2.     public int[] nextGreaterElements(int[] nums) {
3.         int len=nums.length;
4.         Stack<Integer> stack=new Stack<>();
5.         int[] result=new int[len];
6.         Arrays.fill(result,-1);
8.         stack.push(0);
9.         for (int i=1;i<len*2;i++){
10.             if (nums[i%len]<=nums[stack.peek()]){
11.                 stack.push(i%len);
12.             }else {
13.                 while (!stack.isEmpty()&&nums[i%len]>nums[stack.peek()]){
14.                     result[stack.peek()]=nums[i%len];
15.                     stack.pop();
16.                 }
17.                 stack.push(i%len);
18.             }
19.         }
20.         return result;
21.     }
22. }

复制代码

总结：循环都涉及到下标取余数组长度的操作。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。