java 解法, 执行用时: 15 ms, 内存消耗: 41.9 MB, 提交时间: 2023-02-14 09:40:43

class Solution {
    public int longestWPI(int[] hours) {
        int ans = 0, s = 0;
        Map<Integer, Integer> pos = new HashMap<>();
        for (int i = 0; i < hours.length; ++i) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) {
                ans = i + 1;
            } else if (pos.containsKey(s - 1)) {
                ans = Math.max(ans, i - pos.get(s - 1));
            }
            pos.putIfAbsent(s, i);
        }
        return ans;
    }
}

golang 解法, 执行用时: 24 ms, 内存消耗: 6.3 MB, 提交时间: 2023-02-14 09:40:21

func longestWPI(hours []int) (ans int) {
    s := 0
    pos := map[int]int{}
    for i, x := range hours {
        if x > 8 {
            s++
        } else {
            s--
        }
        if s > 0 {
            ans = i + 1
        } else if j, ok := pos[s-1]; ok {
            ans = max(ans, i-j)
        }
        if _, ok := pos[s]; !ok {
            pos[s] = i
        }
    }
    return
}

func max(x, y int) int { if x < y { return y }; return x }

python3 解法, 执行用时: 64 ms, 内存消耗: 15.7 MB, 提交时间: 2023-02-14 09:33:12

# 前缀和 + 哈希表
class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ans = s = 0
        pos = {}
        for i, x in enumerate(hours):
            s += 1 if x > 8 else -1
            if s > 0:
                ans = i + 1
            elif s - 1 in pos:
                ans = max(ans, i - pos[s - 1])
            if s not in pos:
                pos[s] = i
        return ans

python3 解法, 执行用时: 84 ms, 内存消耗: 15.9 MB, 提交时间: 2023-02-14 09:29:58

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        score = [1 if hour > 8 else -1 for hour in hours]
        # 前缀和
        presum = [0] * (n + 1)
        for i in range(1, n + 1):
            presum[i] = presum[i - 1] + score[i - 1]
        ans = 0
        stack = []
        # 顺序生成单调栈，栈中元素从第一个元素开始严格单调递减，
        # 最后一个元素肯定是数组中的最小元素所在位置
        for i in range(n + 1):
            if not stack or presum[stack[-1]] > presum[i]:
                stack.append(i)
        # 倒序扫描数组，求最大长度坡
        i = n
        while i > ans:
            while stack and presum[stack[-1]] < presum[i]:
                ans = max(ans, i - stack[-1])
                stack.pop()
            i -= 1
        return ans