Leetcode: 【每日一题】- 2020-08-31 - Largest Range

[azl397985856]

Write a function that takes in an array of integers and returns an array of length 2 representing the largest range of integers contained in that array.

The first number in the output array should be the first number in the range, while the second number should be the last number in the range.

A range of numbers is defined as a set of numbers that come right after each other in the set of real integers. For instance, the output array [2, 6] represents the range {2, 3, 4, 5, 6}, which is a range of length 5. Note that numbers don't need to be sorted or adjacent in the input array in order to form a range.

You can assume that there will only be one largest range.

Sample Input：

array = [1, 11, 3, 0, 15, 5, 2, 4, 10, 7, 12, 6]

Sample Output：

[0, 7]

[azl397985856]

思路

离散化即可。 唯一需要注意的是负数的情况。

• 将数据离散化到 [0, upper - lower + 1]的数组上，索引为值，值为 1（二值化）。其中 upper 为 数组的最大值， lower 为数组的最小值。
• 滑动窗口思路计算最大的连续 1 即可。

代码

def largestRange(array):
    upper, lower = max(array), min(array)
    temp = [0] * (upper - lower + 1)
    l = cnt = ans = 0
    for i in range(len(array)):
        temp[array[i] - lower] = 1
    for i in range(len(temp)):
        cnt += temp[i]
        if temp[i] == 0:
            cnt = 0
        if cnt > ans:
            ans = cnt
            l = i - cnt + 1
    return [l + lower, l + ans + lower - 1]

复杂度分析

• 时间复杂度：$O(upper - lower)$，其中 upper 为 数组的最大值， lower 为数组的最小值。
• 空间复杂度：$O(upper - lower)$，其中 upper 为 数组的最大值， lower 为数组的最小值。

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

[feikerwu]

思路:

1. 用一个hashmap一次遍历将所有的数存起来
2. 遍历数据，对每个出现的数，如果这个数出现在range内，那么它肯定有一个线段的上边界和下边界，从当前数向上或者向下在hashmap内寻找，找到上下界，根据线段长度更新最长区间。
3. 将2中遍历过的数从hashmap去掉，避免重复计算

function largestRange(array) {
  let map = {}
  for (let num of array) {
    map[num] = 1
  }

  let [start, end] = [array[0], array[0]]
  for (let cur of array) {
    if (map[cur]) {
      let [newStart, newEnd] = [cur, cur]
      while (map[++newEnd]) {
        map[newEnd] = 0
      }
      while (map[--newStart]) {
        map[newStart] = 0
      }

      if (newEnd - newStart - 2 > end - start) {
        start = newStart + 1
        end = newEnd - 1
      }
    }
  }

  return [start, end]
}

// Do not edit the line below.
exports.largestRange = largestRange

空间复杂度: $O(n)$, n为数组长度
时间复杂度: $O(n)$, n为数组长度

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.