6080. 使数组按非递减顺序排列
给你一个下标从 0 开始的整数数组
nums。在一步操作中，移除所有满足nums[i - 1] > nums[i]的nums[i]，其中0 < i < nums.length。重复执行步骤，直到
nums变为 非递减 数组，返回所需执行的操作数。示例 1：
输入：nums = [5,3,4,4,7,3,6,11,8,5,11] 输出：3 解释：执行下述几个步骤： - 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11] - 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11] - 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11] [5,7,11,11] 是一个非递减数组，因此，返回 3 。
讯享网示例 2：
讯享网输入：nums = [4,5,7,7,13] 输出：0 解释：nums 已经是一个非递减数组，因此，返回 0 。提示：
1 <= nums.length <= 1051 <= nums[i] <= 109
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/steps-to-make-array-non-decreasing/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
赛后听说链表模拟能写，随便改了改就过了，我真是太笨了
1. 建立链表尾节点
2. 倒查数组，把每个节点接在后一个节点的前面（例如 5 4 3,4 和 3 本轮都可以删除，倒着放可以满足一轮同时删掉 4 和 3）
3. 如果是合适的节点，加入队列
4. 类似层次遍历，一层层查，还比下一个大，再放回去
5. 每经过一层，证明经过一**作，操作数加 1
细节
一定要倒着查，正着删会漏掉，如 5 4 3 ，4 删掉了，后面在队列中再拿到4，不好处理
class Solution { public int totalSteps(int[] nums) { Node last = new Node(0); Node curr = last; Queue<Node> queue = new LinkedList<>(); int n = nums.length; for(int i = n-1; i >= 0; i--){ int num = nums[i]; Node v = new Node(num); v.next = curr; curr = v; if(curr.next!=last && curr.val > curr.next.val){ queue.offer(curr); } } int ans = 0; while (!queue.isEmpty()){ ++ans; int size = queue.size(); for(int i = 0; i < size; i++){ Node node =queue.poll(); node.next = node.next.next; if(node.next!=last&&node.val > node.next.val){ queue.offer(node); } } } return ans; } class Node{ Node next; int val; public Node(int val){ this.val = val; } } }感想：对于一个方法死磕写不出来的（尤其像贪心、单调栈、动态规划），可尝试换换思路
评论🌹点赞👍收藏✨关注👀，是送给作者最好的礼物，愿我们共同学习，一起进步
如果对作者发布的内容感兴趣，可点击下方关注公众号 钰娘娘知识汇总 查看更多作者文章哦！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/47161.html