1574.删除最短的子数组使剩余数组有序.md

1574.删除最短的子数组使剩余数组有序

/*
 * @lc app=leetcode.cn id=1574 lang=typescript
 *
 * [1574] 删除最短的子数组使剩余数组有序
 */

// @lc code=start
function findLengthOfShortestSubarray(arr: number[]): number {}
// @lc code=end

解法 1: 分类讨论

function findLengthOfShortestSubarray(arr: number[]): number {
  const n = arr.length
  let res = 1
  for (let i = 1; i < n; i++) {
    if (arr[i] < arr[i - 1]) break
    res = i + 1
  }
  if (res === n) return 0
  for (let i = n - 2; i >= 0; i--) {
    if (arr[i] > arr[i + 1]) break
    res = Math.max(res, n - i)
  }
  for (let i = 0, j = n - 1; i < n; i++) {
    if (i && arr[i] < arr[i - 1]) break
    while (j > i + 1 && arr[j] >= arr[j - 1] && arr[j - 1] >= arr[i]) j--
    while (j < n && arr[j] < arr[i]) j++
    if (j === n) break
    res = Math.max(res, n - j + i + 1)
  }
  return n - res
}

Case

test.each([
  { input: { arr: [1, 2, 3, 10, 4, 2, 3, 5] }, output: 3 },
  { input: { arr: [5, 4, 3, 2, 1] }, output: 4 },
  { input: { arr: [1, 2, 3] }, output: 0 },
])('input: arr = $input.arr', ({ input: { arr }, output }) => {
  expect(findLengthOfShortestSubarray(arr)).toEqual(output)
})