• [每日两题系列]刷算法题咯~~


            本系列所选题目均来自力扣或者牛客网站. 所选题目主要是以其中的简单题为主, 中等题为辅, 包含少数困难题(原因是: 本人目前能力还不够~ ). 开展这个系列的目的是督促自己, 在暑假的时间里也要保持有一定的刷题量, 拒绝摆烂~
            话不多说, 直接开刷~ 今天的两道题都比较有意思~

    用栈操作构建数组

            题目描述: 给你一个目标数组 target 和一个整数 n。每次迭代,需要从 list = {1,2,3…, n} 中依序读取一个数字。
            请使用下述操作来构建目标数组 target :
            Push:从 list 中读取一个新元素, 并将其推入数组中。
            Pop:删除数组中的最后一个元素。
            如果目标数组构建完成,就停止读取更多元素。
            题目数据保证目标数组严格递增,并且只包含 1 到 n 之间的数字。
            请返回构建目标数组所用的操作序列。

    解题思路:
            (1) 刚开始看到这道题还是比较懵的, 因为有一个示例是这样子的: 输入:target = [1,2], n = 4 ; 输出:[“Push”,“Push”] . 我在想: 根据上面的示例来说, 这里的输出结果不应该是[“Push”,“Push”,“Push”,“Pop”,“Push”,“Pop”]或者是其他的, 总想着应该先要凑到4, 然后再删除啥的. 之后看解释是说: 只需要读取前 2 个数字就可以停止。所以这样来说, 我们就还要另外考虑这种情况…
            (2) 其实抛开上面的特殊情况, 我们可以写出一代版本的代码, 思路是 — 从1遍历到n, 看看数组中是否有缺少的数字(或者是不连续的数字), 如若相邻两个数字是连续的, 那么直接在顺序表中添加"Push"即可; 如若是不连续的(与目标的数字没有对应), 那么在顺序表中加上"Push"和"Pop"即可.
            (3) 考虑到上面还有一种特殊情况, 由于只有当单纯地"Push"的时候, 所给数组的下标才会往后走, 这时候就可以有一个条件: 当下标的值与数组长度相等的时候, 无论是否到达了n, 都可以直接返回.

    实现代码:

    class Solution {
        public List<String> buildArray(int[] target, int n) {
            List<String> ret=new ArrayList<>();
            int count=0;
            for(int i=1;i<=n;i++){
                if(count==target.length){
                    break;
                }
                if(target[count]==i){
                    ret.add("Push");
                    count++;
                }else{
                    ret.add("Push");
                    ret.add("Pop");
                }
            }
            return ret;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    下一个更大元素I

            题目描述: nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
            给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。
            对于每个 0 <= i < nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素,那么本次查询的答案是 -1 。
            返回一个长度为 nums1.length 的数组 ans 作为答案,满足 ans[i] 是如上所述的 下一个更大元素 。

    解题思路1:
            (1) 看到这样的提, 我的第一感觉就是直接暴力求解.
            (2) 我一上来就直接遍历数组1, 在数组1中遍历数组2, 得到想要的值, 最后赋回给数组1对应的位置.
            (3) 最后返回数组1即可. 虽然思路非常简单, 但是这里的时间复杂度就会达到了O(mn).

    实现代码:

    class Solution {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int len1=nums1.length;
            int len2=nums2.length;
            for(int i=0;i<len1;i++){
                int j=0;
                while(nums1[i]!=nums2[j]){
                    j++;
                }
                int k=0;
                for(k=j+1;k<len2;k++){
                    if(nums2[k]>nums2[j]){
                        nums1[i]=nums2[k];
                        break;
                    }
                }
                if(k==len2){
                    nums1[i]=-1;
                }
            }
            return nums1;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    解题思路2:
            (1) 所以下来我又看了官方给的题解, 使用的是单调栈+哈希表, 这属实是我意想不到的, 为了看懂它的代码, 还是需要拿出画图板画一会的, 接下来就来讲讲这种思路.
            (2) 既然是单调栈+哈希表, 那么就需要先定义一个哈希表和一个栈. 大体的思路是: 从后往前遍历数组2, 通过单调栈来确定一个数的下一个比它大的数是谁, 然后使用哈希表来将数组2中每个元素以及对应的下一个比自身答的数用键值对存储起来. 因为题目说了, 数组1中的元素在数组2中都有包含, 所以用前面得出的哈希表来进行查找对应的值即可.
            (3) 执行过程细节解析: 最后一个元素对应的一定就是-1, 然后把这个元素压入栈底. 循环看数组2中的前一个元素是否比栈顶的元素大, 如若大, 那么将栈顶的元素出栈, 再接着判断新的栈顶元素(栈中有元素的情况下), 如此往复, 直到该元素比栈顶元素小(或者整个栈被出空了), 然后把这个元素对应的val值赋为栈顶元素的值(如果栈是空, 则赋为-1), 最后将这个元素压入栈中, 再执行下一次循环.
            (4) 这样的代码时间复杂度就只变成了O(m+n).
            注意: 在这道题的解法下面我还看到评论: “一但要求下一个更大的元素,就是用单调栈解,力扣题库相似的题目都是这个解法。” 所以说, 我们把这种单调栈的解法记住还是非常有必要的~

    class Solution {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            Map<Integer,Integer> map=new HashMap<>();
            Stack<Integer> stack=new Stack<>();
            int len1=nums1.length;
            int len2=nums2.length;
            for(int i=len2-1;i>=0;i--){
                int num=nums2[i];
                while(!stack.isEmpty()&&num>stack.peek()){
                    stack.pop();
                }
                map.put(num,stack.isEmpty()?-1:stack.peek());
                stack.push(num);
            }
            for(int i=0;i<len1;i++){
                nums1[i]=map.get(nums1[i]);
            }
            return nums1;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    重要的事情说三遍:
            求下一个更大元素 用单调栈!!!

            求下一个更大元素 用单调栈!!!

            求下一个更大元素 用单调栈!!!

  • 相关阅读:
    LeetCode(力扣)216. 组合总和 IIIPython
    千兆以太网(一)——RGMII与GMII接口
    服务器被黑该如何查找入侵痕迹以及如何防御攻击
    C++中使用boost库存取ini结构化文本文件
    LeetCode地平线专场——第308场周赛题解
    数据库及ADO.NET学习(四)
    你需要了解的关于 React 的知识 useEvent钩子 RFC
    前端代码规范
    视频集中存储/直播点播平台EasyDSS点播文件分类功能新升级
    SQL编程 Task05.SQL高级处理
  • 原文地址:https://blog.csdn.net/Faith_cxz/article/details/125894934