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

链接：1124.表现良好的最长时间段
难度：Medium
标签：栈、数组、哈希表、前缀和、单调栈
简介：给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

题解 1 - typescript

• 编辑时间：2021-03-20
• 执行用时：1044ms
• 内存消耗：42.8MB
• 编程语言：typescript
• 解法介绍：前缀和。

function longestWPI(hours: number[]): number {
  hours = hours.map(v => (v > 8 ? 1 : -1));
  const len = hours.length;
  const sums = [0];
  let sum = 0;
  hours.forEach(hour => sums.push((sum += hour)));
  let max = 0;
  for (let i = 1; i < len + 1; i++) {
    for (let j = 0; j < i; j++) {
      if (sums[i] - sums[j] > 0) max = Math.max(max, i - j);
    }
  }
  return max;
}

题解 2 - rust

• 编辑时间：2023-02-14
• 执行用时：12ms
• 内存消耗：2.4MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn longest_wpi(hours: Vec<i32>) -> i32 {
        use std::collections::VecDeque;
        let n = hours.len();
        let mut ans = 0;
        let mut sums = vec![0; 1];
        for h in hours {
            let h: i32 = if h > 8 { 1 } else { -1 };
            sums.push(sums.last().unwrap() + h);
        }
        let mut s = VecDeque::<usize>::new();
        s.push_back(0);
        for i in 1..=n {
            if sums[*s.back().unwrap()] > sums[i] {
                s.push_back(i);
            }
        }
        let mut i = n;
        while i >= 1 {
            while !s.is_empty() && sums[*s.back().unwrap()] < sums[i] {
                ans = ans.max(i as i32 - s.pop_back().unwrap() as i32);
            }
            i -= 1;
        }
        ans
    }
}

题解 3 - python

• 编辑时间：2023-02-14
• 执行用时：72ms
• 内存消耗：15.7MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        ans = 0
        sums = [0]
        for h in hours:
            v = -1
            if (h > 8):
                v = 1
            sums.append(sums[-1] + v)
        s = [0]
        for i in range(1, n+1):
            if sums[s[-1]] > sums[i]:
                s.append(i)
        for i in range(n, 0, -1):
            while len(s) and sums[s[-1]] < sums[i]:
                ans = max(ans, i - s.pop())
        return ans

题解 4 - cpp

• 编辑时间：2023-02-14
• 执行用时：32ms
• 内存消耗：23.3MB
• 编程语言：cpp
• 解法介绍：单调栈，找出最远最小的值。

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size(), ans = 0;
        for (auto &h : hours) h = h > 8 ? 1 : -1;
        vector<int> sums(1, 0);
        for (auto &h : hours) sums.push_back(sums.back() + h);
        stack<int> s; s.push(0);
        for (int i = 1; i <= n; i++) {
            if (sums[s.top()] > sums[i]) s.push(i);
        }
        for (int i = n; i >= 1; i--) {
            while (s.size() && sums[s.top()] < sums[i]) {
                ans = max(ans, i - s.top());
                s.pop();
            }
        }
        return ans;
    }
};