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

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 哈希表（推荐）
相似题目

题目描述

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

思路分析

解法一：前缀和 + 哈希表（推荐）

核心思路：

将工时 > 8 记为 +1，否则记为 -1。

维护前缀和 sum，若 sum > 0 则当前前缀即为候选答案。

若 sum <= 0，查找 sum - 1 最早出现的位置以更新答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于保存前缀和最早位置。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestWPI(int[] hours) {
        Map<Integer, Integer> first = new HashMap<>();
        int sum = 0;
        int best = 0;

        for (int i = 0; i < hours.length; i++) {
            sum += hours[i] > 8 ? 1 : -1;

            if (sum > 0) {
                best = i + 1;
            } else {
                if (first.containsKey(sum - 1)) {
                    best = Math.max(best, i - first.get(sum - 1));
                }
            }

            first.putIfAbsent(sum, i);
        }

        return best;
    }
}

func longestWPI(hours []int) int {
	first := make(map[int]int)
	sum := 0
	best := 0

	for i, h := range hours {
		if h > 8 {
			sum++
		} else {
			sum--
		}

		if sum > 0 {
			best = i + 1
		} else if idx, ok := first[sum-1]; ok {
			if i-idx > best {
				best = i - idx
			}
		}

		if _, ok := first[sum]; !ok {
			first[sum] = i
		}
	}

	return best
}

相似题目

题目	难度	考察点
1124. 表现良好的最长时间段	中等	前缀和
525. 连续数组	中等	前缀和
560. 和为 K 的子数组	中等	前缀和
930. 和相同的二元子数组	中等	前缀和
1524. 和为奇数的子数组数目	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/89301875