904.水果成篮.md

904.水果成篮

/*
 * @lc app=leetcode.cn id=904 lang=typescript
 *
 * [904] 水果成篮
 */

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

解法 1: 双指针

function totalFruit(fruits: number[]): number {
  const n = fruits.length
  let res = 0,
    cnt = new Map<number, number>()
  for (let l = 0, r = 0; r < n; r++) {
    const a = fruits[r]
    cnt.set(a, (cnt.get(a) ?? 0) + 1)
    while (cnt.size > 2) {
      const a = fruits[l++]
      cnt.set(a, cnt.get(a)! - 1)
      if (!cnt.get(a)) cnt.delete(a)
    }
    res = Math.max(res, r - l + 1)
  }
  return res
}

Case

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