首页 > 其他分享 >leet code 581. 最短无序连续子数组

leet code 581. 最短无序连续子数组

时间:2023-12-23 10:04:22浏览次数:49  
标签:leet code end nums int 581 min 数组 stack

581. 最短无序连续子数组

题目描述

给你一个整数数组 nums

你需要找出一个 连续子数组

如果对这个子数组进行升序排序

那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组 并输出它的长度。

示例 1:

输入:nums = [2,6,4,8,10,9,15] 输出:5

解释:你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。

示例 2:

输入:nums = [1,2,3,4] 输出:0

示例 3:

输入:nums = [1] 输出:0

提示:

leet code 581. 最短无序连续子数组_最小值

leet code 581. 最短无序连续子数组_最小值_02

进阶: 你可以设计一个时间复杂度为O(n)的解决方案吗?

题目解析

初步思路--超时的解

  • 首先题目仅要求输出最短子数组的长度
  • 那么仅仅知道子数组左右边界的索引位置即可
  • 利用一个辅助栈来维护递增的序列,栈顶元素最大
  • 如果当前元素,小于栈顶元素那么需要进行交换,找到 当前元素应该处于数组对应的哪一个位置
  • 然后这个时候可以记录更新一下 start、end 的位置

show code

class Solution {
     public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }
        // 用一个栈维护递增序列
        Deque<Integer> stack = new LinkedList<>();
        // 辅助栈,当 遇到元素小于 stack.peek() 的时候辅助交换元素
        Deque<Integer> temporary = new LinkedList<>();
        // start:记录 符合要求的子数组的开始位置
        // end :记录符合要求的子数组的结束位置
        int start = n, end = 0;
        for (int num : nums) {
            // 如果需要进行元素交换排序
            while (!stack.isEmpty() && num < stack.peek()) {
                temporary.push(stack.pop());
            }
            // 记录一次 start 的位置
            if (!temporary.isEmpty()) {
                start = Math.min(start, stack.size());
            }
            stack.push(num);
            // 不断记录更新  end 的位置.
            if (!temporary.isEmpty()) {
                end = stack.size() + temporary.size() - 1;
            }
            while (!temporary.isEmpty()) {
                stack.push(temporary.pop());
            }
        }
        return start == n ? 0 : (end - start + 1);
    }
}
  • 但是超时了
  • 因为两个栈来互相交换元素的过程太过耗时

优化解-O(n)时间复杂度

  • 如果考虑只遍历常数次数组就能够得到最终结果呢?
  • 首先我们仅仅需要得到左右边界
  • 所以,最终应该要求得 “最短无序连续子数组” 中最大值和最小值对应的索引位置
  • 那么这个 “最短无序连续子数组” 具有什么性质呢?
  1. 其位于原数组的中间
  2. 其最小值 大于 其左段的最大值
  3. 其最大值 小于 其右段的最小值
  1. 那么从左到右维护一个最大值 max,那么在进入右段之前,所有的值都小于 max
  2. 那么右边界end对应的就是最后一个小于max的元素
  3. 同理,从右到左维护一个最小值 min,在进入左段之前,所有的值都大于 min
  4. 那么左边界begin就是最后一个大于 min 元素的位置

show code

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        // 初始化一个最大值和一个最小值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 初始化 begin end 对应 最短连续子数组 的左右边界
        int begin = 0,end = -1;
        // 开始遍历
        for(int i = 0;i < n;i++) {
            // 所有的 nums[i] 小于 max
            // 找到最后一个小于 max 位置的索引
            if(nums[i] < max) {
                end = i;
            } else {
                max = nums[i];
            }

            // 所有的 nums[i] 大于min
            // 寻找最后一个大于 min 位置的索引
            if(nums[n - i - 1] > min) {
                begin = n - i - 1;
            } else {
                min = nums[n - i - 1];
            }
        }
        return end - begin + 1;
    }
}

标签:leet,code,end,nums,int,581,min,数组,stack
From: https://blog.51cto.com/u_16079703/8944241

相关文章

  • PySide6学习笔记(一)VSCode配置
    vscode配置(windows)在vscode中安装Python与QTforPython和coderunner插件(推荐)   Python与QTforPython插件开发PySide必备coderunner(可以右键运行py文件)安装PySide6pipinstallPySide6配置QTforpython插件 点击插件设置-拓展设置找到......
  • 『LeetCode』3. 无重复字符的最长子串 Longest Substring Without Repeating Characte
    『1』双指针算法我的想法:一般看到字符串子串问题想到用双指针解,看到字符串子序列问题想到用动态规划解。此题用双指针可以很快解题。遍历字符串中的每个字符s.charAt[i],对于每一个i,找到j使得双指针[j,i]维护的是以s.charAt[i]结尾的无重复字符的最长子串,长度为i-j+1,......
  • AtCoder 杂题精选(2023 年末)
    [ABC324G]GenerateArrays第一次知道AtCoder还有这种数据结构题。首先,所谓的“切分序列”是假,实际上只需要记录每个操作后,具体取到的原始数组的值域、下标域是什么。对于给定的下标域,求值域内数的个数,可以使用可持久化线段树,很类似区间第\(k\)大数的思路。对于操作一,考虑......
  • vsCode连接时一直显示正在下载vscode服务器问题
    在服务器执行psaux|grepwget输出为找到有vscode-server的进程,在本地机器浏览器输入vscode-server.tar.gz后面的网址,下载vscode-server-linux-x64.tar.gz记录该条进程的启动命令,并kill该进程kill-9pid通过scp传到工控机清空文件夹,其中bin的子目录为刚才......
  • [LeetCode] 热题100
    128最长连续序列publicclassSolution{publicintlongestConsecutive(int[]nums){if(nums==null||nums.length==0)return0;intans=1;HashMap<Integer,Integer>map=newHashMap<>();for(intnum:......
  • MacOS - 安装多个xcode版本,选择默认启动版本
    1、有时候xcode发布新版本,但是我们项目正要上线,来不及升级xcode版本,怕带来未知的风险,这时候就可以安装多个xcode版本,下载地址https://developer.apple.com/download/more/1.2然后登陆appledeveloper,搜索xcode,即可下载最新版本  1.3下载完成后,将当前低版本的xcod......
  • Codeforces Round 651 (Div. 2)C. Number Game(数学思维数论)
    C.NumberGame我们考虑那些状态是必胜态我的回合时n为奇数(除1外),直接除以n则必胜下面偶数的情况稍复杂偶数我们能进行的操作只有除以一个奇数,需要考虑怎么把当前状态变为对手的必败态偶数一定含2的因子,\(n=2^k*q,q为奇数\)当\(k=1时如果q\)是一个质数那么只能除一次q这样......
  • Leetcode—矩阵置零
    矩阵置零给定一个mxn的矩阵,如果一个元素为0,则将其所在行和列的所有元素都设为0。请使用原地算法。示例1:输入:输入:matrix=[[1,1,1],[1,0,1],[1,1,1]]输出:[[1,0,1],[0,0,0],[1,0,1]]示例2:输入:matrix=[[0,1,2,0],[3,4,5,2],[1,3,1,5]]输出:[[0,0,0,0],[0,4,......
  • Leetcode 2521. 数组乘积中的不同质因数数目
    https://leetcode.cn/problems/distinct-prime-factors-of-product-of-array/description/给你一个正整数数组nums,对nums所有元素求积之后,找出并返回乘积中不同质因数的数目。注意:质数是指大于1且仅能被1及自身整除的数字。如果val2/val1是一个整数,则整数val......
  • 『LeetCode』2. 两数相加 Add Two Numbers
    『1』迭代法classSolution{//Iteration//Nisthesizeofl1,Misthesizeofl2//TimeComplexity:O(max(M,N))//SpaceComplexity:O(max(M,N))ifdummyiscountedelseO(1)publicListNodeaddTwoNumbers(ListNodel1,ListNodel2)......