Leetcode-581 Shortest Unsorted Continuous Subarray

发表于 | 分类于 | 次

Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

Example 1

1
2
3
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

解题思路

最短未排序连续子数组的范围取决于其中最小元素 minNum 与最大元素 maxNum 在排序数组中的位置，两个元素在所有违反有序性的位置产生。遍历数组，对于所有 nums[i]<nums[i-1] 的位置，更新 minNum 和 maxNum 。之后，找出 minNum 和 maxNum 在排序数组中的位置，并返回索引之差。

复杂度分析

  • 时间复杂度：$O(n)$，遍历两次数组。
  • 空间复杂度：$O(1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	int findUnsortedSubarray(vector<int>& nums) {
		int n = nums.size();
		int minNum = INT_MAX, maxNum = INT_MIN;
		for (int i = 1; i < n; ++i) {
			if (nums[i] < nums[i - 1]) {
				minNum = min(minNum, nums[i]);
				maxNum = max(maxNum, nums[i - 1]);
			}
		}
		int l = 0, r = n - 1;
		while (l < r&&nums[l] <= minNum) ++l;
		while (l < r&&nums[r] >= maxNum) --r;

		return r > l ? r - l + 1 : 0;
	}
};