D50|单调栈

发布时间:2024年01月04日

739.每日温度

初始思路:

暴力解法但是会超时。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        for(int i = 0;i<temperatures.length;i++){
            for(int j = i;j<temperatures.length;j++){
                if(temperatures[j]>temperatures[i]){
                    answer[i] = j-i;
                    break;
                }

            }
        }
        return answer;
    }
}

题解复盘:

首先了解一下单调栈这部分的数据结构

[数据结构]——单调栈-CSDN博客

  1. 单调栈里存放的元素是什么?

单调栈里只需要存放元素的下标i就可以了,如果需要使用对应的元素,直接T[i]就可以获取。

? ? ?2. 单调栈里元素是递增呢? 还是递减呢?

注意以下讲解中,顺序的描述为 从栈头到栈底的顺序,因为单纯的说从左到右或者从前到后,不说栈头朝哪个方向的话,大家一定比较懵。

这里我们要使用递增循序(再强调一下是指从栈头到栈底的顺序),因为只有递增的时候,栈里要加入一个元素i的时候,才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

即:如果求一个元素右边第一个更大元素,单调栈就是递增的,如果求一个元素右边第一个更小元素,单调栈就是递减的。

?

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Stack<Integer> st= new Stack<>();
        st.push(0);
        for(int i = 1;i<temperatures.length;i++){
            if(temperatures[i]<= temperatures[st.peek()]){
                    st.push(i);
            }else
            {
                while(!st.isEmpty()&&temperatures[i]>temperatures[st.peek()]){

                    answer[st.peek()] = i- st.pop();
                }
                st.push(i);
            }


        }
        return answer;
    }
}

栈内存放的是下标,主要为了记录遍历过的数据,且为了后续方便求下标的距离,如果当前数组元素大于栈顶元素的话,表示该元素是数组内下标元素的最右边第一个最大的值,所以在answer中存放结果,并且pop()栈顶元素,这个过程一直循环到小于栈顶元素,然后就将该元素push进去。


496.下一个更大元素 I

初始思路:

? ? ? ? 初始化一个answer数组,answer数组的大小和nums1相同,我觉得都初始化为-1就很好.

? ? ? ? 然后当nums2中的元素等于nums1的元素时,存入栈,如果后面nums2的元素大于栈顶元素就把结果存入answer。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] answer = new int[nums1.length];
        Stack<Integer> st = new Stack<>();
        Arrays.fill(answer,-1);
        for(int i = 0;i<nums1.length;i++){
            for(int j= 0;j<nums2.length;j++){
                if(j==0&&!st.isEmpty()){st.pop();}
                if(nums2[j]==nums1[i]){
                    st.push(nums2[j]);
                    System.out.println(st.peek());
                }
                else if(!st.isEmpty()&&nums2[j]>st.peek()){
                    System.out.println("j"+nums2[j]);
                    System.out.println("stpeek"+st.peek());
                        answer[i] = nums2[j];
                        st.pop();
                }

            }
        }
        return answer;
        
    }
}

没太感觉出来单调栈用在哪里了。

题解复盘:?

1.用map来做映射:

unordered_map<int, int> umap; // key:下标元素,value:下标
for (int i = 0; i < nums1.size(); i++) {
    umap[nums1[i]] = i;
}
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> temp = new Stack<>();
        int[] res = new int[nums1.length];
        Arrays.fill(res,-1);
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            hashMap.put(nums1[i],i);
        }
        temp.add(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[temp.peek()]) {
                temp.add(i);
            } else {
                while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {
                    if (hashMap.containsKey(nums2[temp.peek()])){
                        Integer index = hashMap.get(nums2[temp.peek()]);
                        res[index] = nums2[i];
                    }
                    temp.pop();
                }
                temp.add(i);
            }
        }

        return res;
    }
}

?意思就是在nums2中做单调栈任务,然后再将该元素映射回nums1中寻找其在nums1中的角标(HashMap),再填写在结果数组中。

文章来源:https://blog.csdn.net/Q77ian/article/details/135396220
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。