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

今日收获：单调栈理论，每日温度，下一个更大元素Ⅰ，下一个更大元素Ⅱ

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

应用场景：一维数组寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置

存放的元素：数组下标

递增还是递减：单调递增栈（从栈顶到栈底）求右边第一个比自己大的（遍历发现比自己大的元素）；单调递减栈求右边第一个比自己小的（遍历的目的是发现比自己小的元素）

2. 每日温度

题目链接：739. - 力扣（LeetCode）

思路：用单调递增栈。如果当前元素比栈顶元素小，直接加入栈；反之记录结果，并不断弹出栈中比当前元素小的元素。

方法：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len=temperatures.length;
        Stack<Integer> stack=new Stack<>();
        int[] result=new int[len];

        stack.push(0);
        for (int i=1;i<len;i++){
            if (temperatures[i]<=temperatures[stack.peek()]){
                stack.push(i);  // 加入更小的元素
            }else{
                // 一直弹出比当前元素小的并记录
                while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){
                    result[stack.peek()]=i-stack.peek();
                    stack.pop();
                }
                stack.push(i);  // 加入当前下标
            }
        }

        return result;
    }
}

3. 下一个更大元素Ⅰ

题目链接：496. - 力扣（LeetCode）

思路：和每日温度差不多，只不过在遇到目标元素时，需要判断栈顶元素是否在nums1中。这需要利用map映射存储nums1的值和下标。存储值是为了快速判断当前值是否在nums1中，存储的下标对应结果数组的下标。

方法：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1=nums1.length;
        int len2=nums2.length;

        int[] result=new int[len1];
        Arrays.fill(result,-1);  // 最后栈中留下的元素默认-1

        // 记录数组1中值和下标的对应关系，便于判断当前元素是否存在于nums1中，下标对应结果的下标
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<len1;i++){  
            map.put(nums1[i],i);
        }

        // 求nums2中比当前元素大的右边第一个元素
        Stack<Integer> stack=new Stack<>();
        stack.push(0);
        for (int i=1;i<len2;i++){
            if (nums2[i]<=nums2[stack.peek()]){
                stack.push(i);
            }else {
                while (!stack.isEmpty()&&nums2[i]>nums2[stack.peek()]){
                    if (map.containsKey(nums2[stack.peek()])){  // 收集结果
                        int index=map.get(nums2[stack.peek()]);
                        result[index]= nums2[i];
                    }
                    stack.pop();
                }
                stack.push(i);
            }
        }

        return result;
    }
}

总结：Arrays.fill(数组，填充值) 可以用于Java中数组的初始化。

4. 下一个更大元素Ⅱ

题目链接：503. - 力扣（LeetCode）

思路：遍历两倍长度的数组，求当前元素的值时将下标 i 取余数组长度，其余的思路和每日温度相同。

方法：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int len=nums.length;
        Stack<Integer> stack=new Stack<>();
        int[] result=new int[len];
        Arrays.fill(result,-1);

        stack.push(0);
        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;
    }
}

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

原文地址：https://blog.csdn.net/qq_56221558/article/details/142314713

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！