LeetCode 581. 最短无序连续子数组

Categories:

题目描述
思路分析
1. 解法一：扫描边界（推荐）
相似题目

题目描述

✅ 581. 最短无序连续子数组

思路分析

解法一：扫描边界（推荐）

核心思路：

从左向右维护当前最大值，若 nums[i] < max，说明右边界需至少到 i。

从右向左维护当前最小值，若 nums[i] > min，说明左边界需至少到 i。

若右边界未更新，数组已整体有序。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int right = -1;
        int left = -1;

        // 从左向右扫描确定右边界
        for (int i = 0; i < n; i++) {
            max = Math.max(max, nums[i]);
            if (nums[i] < max) {
                right = i;
            }
        }

        // 从右向左扫描确定左边界
        for (int i = n - 1; i >= 0; i--) {
            min = Math.min(min, nums[i]);
            if (nums[i] > min) {
                left = i;
            }
        }

        if (right == -1) {
            return 0;
        }
        return right - left + 1;
    }
}

func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	maxVal := -1 << 60
	minVal := 1<<60 - 1
	left := -1
	right := -1

	// 从左向右扫描确定右边界
	for i := 0; i < n; i++ {
		if nums[i] > maxVal {
			maxVal = nums[i]
		}
		if nums[i] < maxVal {
			right = i
		}
	}

	// 从右向左扫描确定左边界
	for i := n - 1; i >= 0; i-- {
		if nums[i] < minVal {
			minVal = nums[i]
		}
		if nums[i] > minVal {
			left = i
		}
	}

	if right == -1 {
		return 0
	}
	return right - left + 1
}

相似题目

题目	难度	考察点
769. 最多能完成排序的块	中等	贪心、数组
768. 最多能完成排序的块 II	困难	贪心、数组
674. 最长连续递增序列	简单	数组扫描
300. 最长递增子序列	中等	动态规划
912. 排序数组	中等	排序、数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/55935806