1330.翻转子数组得到最大的数组值.md

1330.翻转子数组得到最大的数组值

/*
 * @lc app=leetcode.cn id=1330 lang=typescript
 *
 * [1330] 翻转子数组得到最大的数组值
 */

// @lc code=start

function maxValueAfterReverse(nums: number[]): number {}
// @lc code=end

解法 1: 分类讨论+线段树

/**
 *
 * 思路：
 * 对于翻转的子数组 [i,j] 来说，翻转之前是 $|nums[i]-nums[i-1]| + |nums[j]-nums[j+1]|$
 * 翻转后是 $|nums[i]-nums[j+1]| + |nums[j]-nums[i-1]|$
 * 假设从左到右的四个点分别是 a,b,c,d
 * 对于 c<d 的情况，只有 a<b<c<d 和 c<d<a<b 两种情况会增加
 * 对于 c>d 的情况，只有 a<b<d<c 和 d<c<a<b 两种情况会增加
 * 所以对于每种情况，只要能够分别获取前另外两种情况的最大值，就能够得到当前情况的最大值
 * 情况      翻转前  ->  翻转后   ->  增加值
 * a<b<c<d  b-a+d-c     d-b+c-a     2*(c-b)
 * c<d<a<b  b-a+d-c     b-d+a-c     2*(a-d)
 * b<a<c<d  a-b+d-c     d-b+c-a     2*(c-a)
 * c<d<b<a  a-b+d-c     b-d+a-c     2*(b-d)
 *
 * a<b<d<c  b-a+c-d     d-b+c-a     2*(d-b)
 * d<c<a<b  b-a+c-d     b-d+a-c     2*(a-c)
 * b<a<d<c  a-b+c-d     d-b+c-a     2*(d-a)
 * d<c<b<a  a-b+c-d     b-d+a-c     2*(b-c)
 * 边界条件，对于 i===0 和 i===n-1 时要特殊处理
 */
function maxValueAfterReverse(nums: number[]): number {
  const n = nums.length,
    MAX = Math.max(...nums) + 10,
    MIN = Math.min(...nums) - 10
  let res = 0
  const abamax = new SegTree(MIN, MAX, (a, b) => Math.max(a, b), -Infinity),
    abbmin = new SegTree(MIN, MAX, (a, b) => Math.min(a, b), Infinity),
    baamin = new SegTree(MIN, MAX, (a, b) => Math.min(a, b), Infinity),
    babmax = new SegTree(MIN, MAX, (a, b) => Math.max(a, b), -Infinity)

  for (let i = 1; i < n; i++) {
    if (i >= 2 && i < n - 1) {
      if (nums[i] <= nums[i + 1]) {
        let min = abbmin.query(MIN, nums[i])
        if (min !== Infinity) {
          res = Math.max(res, 2 * (nums[i] - min))
        }
        let max = abamax.query(nums[i + 1], MAX)
        if (max !== -Infinity) {
          res = Math.max(res, 2 * (max - nums[i + 1]))
        }
        min = baamin.query(MIN, nums[i])
        if (min !== Infinity) {
          res = Math.max(res, 2 * (nums[i] - min))
        }
        max = babmax.query(nums[i + 1], MAX)
        if (max !== -Infinity) {
          res = Math.max(res, 2 * (max - nums[i + 1]))
        }
      } else {
        let min = abbmin.query(MIN, nums[i + 1])
        if (min !== Infinity) {
          res = Math.max(res, 2 * (nums[i + 1] - min))
        }
        let max = abamax.query(nums[i], MAX)
        if (max !== -Infinity) {
          res = Math.max(res, 2 * (max - nums[i]))
        }
        min = baamin.query(MIN, nums[i + 1])
        if (min !== Infinity) {
          res = Math.max(res, 2 * (nums[i + 1] - min))
        }
        max = babmax.query(nums[i], MAX)
        if (max !== -Infinity) {
          res = Math.max(res, 2 * (max - nums[i]))
        }
      }
    }
    if (nums[i] >= nums[i - 1]) {
      abamax.update(nums[i], nums[i], nums[i - 1])
      abbmin.update(nums[i], nums[i], nums[i])
    } else {
      baamin.update(nums[i - 1], nums[i - 1], nums[i - 1])
      babmax.update(nums[i - 1], nums[i - 1], nums[i])
    }
  }
  for (let i = 1; i < n; i++) {
    const d = Math.abs(nums[i] - nums[0]) - Math.abs(nums[i] - nums[i - 1])
    res = Math.max(res, d)
  }
  for (let i = n - 2; i >= 0; i--) {
    const d = Math.abs(nums[i] - nums[n - 1]) - Math.abs(nums[i] - nums[i + 1])
    res = Math.max(res, d)
  }
  let sum = 0
  for (let i = 1; i < n; i++) {
    sum += Math.abs(nums[i] - nums[i - 1])
  }
  return res + sum
}

type Node = {
  left: Node | null
  right: Node | null
  val: number
}
class SegTree {
  private root: Node
  public update: (x: number, y: number, z: number) => void
  public query: (x: number, y: number) => number
  public constructor(
    private min: number,
    private max: number,
    private comparator: (a: number, b: number) => number,
    private bound: number,
  ) {
    this.root = this._newNode()

    this.update = (x: number, y: number, z: number) => {
      x = Math.max(x, min)
      y = Math.min(y, max)
      this._update(this.root, min, max, x, y, z)
    }
    this.query = (x: number, y: number) => {
      x = Math.max(x, min)
      y = Math.min(y, max)
      return this._query(this.root, min, max, x, y)
    }
  }
  private _newNode(val = this.bound, left = null, right = null) {
    return { val, left, right }
  }

  private _up(node: Node) {
    const { left, right } = node
    if (!left || !right) return

    node.val = this.comparator(left.val, right.val)
  }
  private _update(node: Node | null, l: number, r: number, x: number, y: number, z: number): void {
    if (!node) return

    if (l === x && r === y) {
      node.val = this.comparator(node.val, z)
      return
    }

    const mid = Math.floor((l + r) / 2)
    if (!node.left) {
      node.left = this._newNode()
      node.right = this._newNode()
    }

    if (y <= mid) this._update(node.left, l, mid, x, y, z)
    else if (x > mid) this._update(node.right, mid + 1, r, x, y, z)
    else this._update(node.left, l, mid, x, mid, z), this._update(node.right, mid + 1, r, mid + 1, y, z)

    this._up(node)
  }
  private _query(node: Node | null, l: number, r: number, x: number, y: number): number {
    if (y < x) return this.bound
    if (!node) return this.bound

    if (l === x && r === y) return node.val

    let res = this.bound,
      mid = Math.floor((l + r) / 2)
    if (!node.left) {
      node.left = this._newNode()
      node.right = this._newNode()
    }

    if (y <= mid) res = this._query(node.left, l, mid, x, y)
    else if (x > mid) res = this._query(node.right, mid + 1, r, x, y)
    else res = this.comparator(this._query(node.left, l, mid, x, mid), this._query(node.right, mid + 1, r, mid + 1, y))

    this._up(node)
    return res
  }
}

Case

test.each([
  { input: { nums: [93997, 2877, -93018, -76995, -70679] }, output: 369098 },
  { input: { nums: [2, 4, 9, 24, 2, 1, 10] }, output: 68 },
  { input: { nums: [2, 3, 1, 5, 4] }, output: 10 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(maxValueAfterReverse(nums)).toEqual(output)
})