Medium

题目描述

给你一个整数数组 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

提示：

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5

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

解题思路

解题思路

这道题要找到最短的无序子数组，使得只需要排序这个子数组就能让整个数组有序。

方法一：排序比较法

最直观的思路是将原数组排序，然后比较排序前后的数组，找出第一个和最后一个不同的位置。时间复杂度 O(nlogn)。

方法二：单调栈法 （推荐）

利用单调栈的特性来寻找边界：

  1. 从左到右遍历，用单调递增栈找到需要排序的右边界
  2. 从右到左遍历，用单调递减栈找到需要排序的左边界

核心思想是：如果当前元素破坏了单调性，说明它需要被重新排序。

方法三：双指针优化法

  1. 从左到右找到第一个逆序对的位置
  2. 从右到左找到第一个逆序对的位置
  3. 在这个范围内找到最小值和最大值
  4. 扩展边界，确保最小值和最大值都在正确位置

时间复杂度 O(n)，空间复杂度 O(1)，是最优解法。

代码实现

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int left = -1, right = -1;
        stack<int> st;
        
        // 从左到右，找右边界
        for (int i = 0; i < n; i++) {
            while (!st.empty() && nums[st.top()] > nums[i]) {
                right = max(right, st.top());
                st.pop();
            }
            st.push(i);
        }
        
        // 清空栈
        while (!st.empty()) st.pop();
        
        // 从右到左，找左边界
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && nums[st.top()] < nums[i]) {
                left = min(left == -1 ? st.top() : left, st.top());
                st.pop();
            }
            st.push(i);
        }
        
        return right == -1 ? 0 : right - left + 1;
    }
};

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = -1, -1
        stack = []
        
        # 从左到右，找右边界
        for i in range(n):
            while stack and nums[stack[-1]] > nums[i]:
                right = max(right, stack.pop())
            stack.append(i)
        
        # 清空栈
        stack.clear()
        
        # 从右到左，找左边界
        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] < nums[i]:
                left = min(left if left != -1 else stack[-1], stack.pop())
            stack.append(i)
        
        return 0 if right == -1 else right - left + 1

public class Solution {
    public int FindUnsortedSubarray(int[] nums) {
        int n = nums.Length;
        int left = -1, right = -1;
        Stack<int> stack = new Stack<int>();
        
        // 从左到右，找右边界
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && nums[stack.Peek()] > nums[i]) {
                right = Math.Max(right, stack.Pop());
            }
            stack.Push(i);
        }
        
        // 清空栈
        stack.Clear();
        
        // 从右到左，找左边界
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && nums[stack.Peek()] < nums[i]) {
                left = left == -1 ? stack.Pop() : Math.Min(left, stack.Pop());
            }
            stack.Push(i);
        }
        
        return right == -1 ? 0 : right - left + 1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    let left = -1, right = -1;
    let max = nums[0], min = nums[nums.length - 1];
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < max) {
            right = i;
        }
        max = Math.max(max, nums[i]);
    }
    
    for (let i = nums.length - 2; i >= 0; i--) {
        if (nums[i] > min) {
            left = i;
        }
        min = Math.min(min, nums[i]);
    }
    
    return right == -1 ? 0 : right - left + 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度时间复杂度空间复杂度
单调栈法O(n)O(n)
排序比较法O(nlogn)O(n)
双指针法O(n)O(1)

相关题目