1124.表现良好的最长时间段.md

1124.表现良好的最长时间段

/*
 * @lc app=leetcode.cn id=1124 lang=typescript
 *
 * [1124] 表现良好的最长时间段
 */

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

解法 1: 前缀和 + 单调递减栈

预处理好前缀和 sums 为 [0..i] 区间劳累的天数,假设 [i..j] 要满足表现良好的时间段,则要满足 sums[j]-sum[i-1]>(j-i+1) - (sums[j]-sum[i-1]),可以推导出 2*sums[j]-j>2*sums[i-1]-(i-1),只要满足这个条件的都是表现良好的时间段,时间段长度为 j-(i-1)

我们可以记录一个 pre 数组,其中 pre[i]=2*sums[i]-i,i 表示第 i 天,当我们要确定以 j 结尾的所有时间段中的最长表现良好的时间段,则可以转换为求所有满足 i<j&&pre[i]<pre[j] 中最小的 i,可以注意到如果有两个 pre[i] 相等,我们需要取更小的 i 因为这样能够获得更长的时间段,而如果后面的 pre[i] 更大,则可以不用记录,因为前面更小能获取更长的时间段,所以我们可以记录一个严格单调递减的数组 pre 即可,而因为 pre 具有单调性,我们可以使用二分搜索来加速查找的过程.

function longestWPI(hours: number[]): number {
  // 预处理劳累工作天数的前缀和
  const sums: number[] = []
  for (const hour of hours) {
    sums.push((sums[sums.length - 1] ?? 0) + (hour > 8 ? 1 : 0))
  }

  const pre: number[] = []
  // 单调递减栈,记录的是 pre 中的索引,预置了一个 -1 的索引,找到这个索引,表示 pre[i] 比栈中所有的索引指向的值都要大
  // pre[-1] 取值为 undefind,可以用公式 2*sums[i]-i 求得 pre 值为 1,后面的处理使用 ?? 处理为 1
  let stack: number[] = [-1],
    max = 0
  for (let i = 0; i < sums.length; i++) {
    pre[i] = 2 * sums[i] - i

    // 通过二分搜索,查找小于当前 pre[i] 的值
    let [l, r] = [0, stack.length]
    while (l < r) {
      const mid = (l + r) >> 1
      if ((pre[stack[mid]] ?? 1) < pre[i]) {
        r = mid
      } else {
        l = mid + 1
      }
    }

    // 如果  r 等于 stack.length 说明不存在比当前 pre[i] 小的值,既以 i 结尾的良好时间段为 0
    if (r < stack.length) {
      max = Math.max(max, i - stack[r])
    }

    // 只需要将小于当前栈中最小值的值入栈
    if (pre[i] < (pre[stack[stack.length - 1]] ?? 1)) {
      stack.push(i)
    }
  }

  return max
}

优化

function longestWPI(hours: number[]): number {
  const sums: number[] = []
  for (const hour of hours) {
    sums.push((sums[sums.length - 1] ?? 0) + (hour > 8 ? 1 : 0))
  }

  const pre: number[] = [1]
  let stack: number[] = [0],
    max = 0
  for (let i = 1; i <= sums.length; i++) {
    pre[i] = 2 * sums[i - 1] - (i - 1)
    if (pre[i] < pre[stack[stack.length - 1]]) stack.push(i)
  }
  for (let i = pre.length; i >= 0; i--) {
    while (stack.length && pre[i] > pre[stack[stack.length - 1]]) {
      max = Math.max(max, i - stack[stack.length - 1])
      stack.pop()
    }
  }

  return max
}

解法 2: 贪心

function longestWPI(hours: number[]): number {
  const map = new Map<number, number>()

  let cur = 0,
    max = 0,
    min = Infinity
  for (let i = 0; i < hours.length; i++) {
    hours[i] > 8 ? cur++ : cur--

    if (cur > 0) max = i + 1
    else if (map.has(cur - 1)) max = Math.max(max, i - map.get(cur - 1)!)

    if (cur < min) {
      min = cur
      map.set(cur, i)
    }
  }

  return max
}

解法 3: 双指针

function longestWPI(hours: number[]): number {
  const n = hours.length
  const a = hours.map(a => (a > 8 ? 1 : -1))
  let b: [number, number][] = [[-1, 0]]
  let res = 0,
    sum = 0
  for (let i = 0, j = 0; i < n; i++) {
    sum += a[i]
    if (a[i] === 1) {
      res = Math.max(res, i - b[j][0])
      if (j) j--
    } else {
      if (sum < b[j][1]) {
        j++
        if (j === b.length) {
          b.push([i, sum])
        }
      } else if (sum > b[j][1]) {
        res = Math.max(res, i - b[j][0])
      }
    }
  }
  return res
}

Case

test.each([
  { input: { hours: [9, 6, 6] }, output: 1 },
  { input: { hours: [6, 9, 9] }, output: 3 },
  { input: { hours: [6, 9, 6] }, output: 1 },
  { input: { hours: [6, 6, 9] }, output: 1 },
  { input: { hours: [0, 0, 0, 9, 9, 6, 0, 6, 6, 9] }, output: 3 },
  { input: { hours: [9, 9, 6, 0, 6, 6, 9] }, output: 3 },
  { input: { hours: [6, 6, 6] }, output: 0 },
])('input: hours = $input.hours', ({ input: { hours }, output }) => {
  expect(longestWPI(hours)).toEqual(output)
})