Skip to main content

581. Shortest Unsorted Continuous Subarray

分析


题解

排序法

O(nlgn) 不符合时间要求

function findUnsortedSubarray(nums: number[]): number {
const temp = nums.slice().sort((a, b) => a - b)

let l = -1
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== temp[i]) {
l = i
break
}
}

let r = nums.length
for (let i = nums.length - 1; i >= 0; i--) {
if (nums[i] !== temp[i]) {
r = i
break
}
}

const ans = r - l + 1
return ans > nums.length ? 0 : ans
};

单调栈

O(n)

function findUnsortedSubarray(nums: number[]): number {
// [2,6,4,8,10,9,15]
// 构建递增单调栈(不严格递增) [2, 6] 如果进了个4 -> [2, 4] 弹出 6
// 弹出的元素就是无序的元素
const monoIncressStack = []
let l = nums.length
for (let i = 0; i < nums.length; i++) {
while (monoIncressStack.length && nums[i] < nums[monoIncressStack[monoIncressStack.length - 1]]) {
l = Math.min(l, monoIncressStack.pop())
}
monoIncressStack.push(i)
}

const monoDecressStack = []
let r = -1
for (let i = nums.length - 1; i >= 0; i--) {
while (monoDecressStack.length && nums[i] > nums[monoDecressStack[monoDecressStack.length - 1]]) {
r = Math.max(r, monoDecressStack.pop())
}
monoDecressStack.push(i)
}
return r - l + 1 > 0 ? r - l + 1 : 0
};