题目链接：1124. 表现良好的最长时间段
方法：前缀和 + 单调栈
前缀和简介
对于数组 \(a[n]\)，其前缀和数组 \(s[n + 1]\), \(s[i]\) 表示数组 \(a[0, i - 1]\) 的和，\(1 ≤ i ≤ n\)。
s[0] = 0;
for (int i = 1; i <= n; i ++ ) {
s[i] = s[i - 1] + a[i - 1];
}
当前缀和数组 \(s\) 构建成功后，可以在 \(O(1)\) 的时间内求出，\(a[i, j]\) 的和，\(s[j + 1] - s[i]\)。
解题思路
- 原问题：表现良好时间段—\([l, r]\) 时间段内，劳累的天数 \(>\) 不劳累的天数，且要求 \([l, r]\) 越长越好。
- 由于涉及区间内计数，考虑前缀和算法，可以在 \(O(1)\) 时间内获取任一区间内的和。在此问题中，存在两种状态，设劳累的一天为 \(1\), 不劳累的一天为 \(-1\)，计算 \(hours[n]\) 数组的前缀和数组 \(cnt[n + 1]\) (为了处理边界，前缀和从 \(1\) 开始计算，默认 \(cnt[0] = 0\) )。
- 问题转化：表现良好时间段— \((l, r]\) 时间段内，\(cnt[r] > cnt[l]\)，区间长度为 \(r - l\)。此时问题可以转化为，在 \(cnt\) 数组中，找 \(i < j\)，且 \(cnt[i] < cnt[j]\)，并且 \(j - i\) 尽可能的大。
- 单调栈：初始化栈 \(stk.push(0)\)，对于区间的左端点 \(i\) 选取，若 \(cnt[i] >= stk.pop()\)，不需要入栈，因为一旦有右端点 \(cnt[j] > cnt[i]\)，那么 \(cnt[j] > stk.pop()\)，此时选栈顶坐标作为左端点更远；否则左端点 \(i\) 入栈。
当全部可能的左端点入栈后，为了确保 \([i, j]\) 相差最大，从 \(n->1\) 枚举右端点 \(j\)，若 \(cnt[j] > cnt[stk.top()]\)，则 \((stk.pop(), j]\) 为良好时间段，取 \(ans = max(ans, j - stk.pop())\)，并 \(pop()\) 出栈，继续比较下一个栈顶，当前右端点若不满足条件 \(cnt[j] > cnt[stk.top()]\)，则枚举下一个右端点。
代码
class Solution {
public:
int longestWPI(vector<int>& hours) {
int n = hours.size(), cnt[n + 1], ans = 0; // cnt[i]，表示前i天, 劳累的天数 - 不劳累的天数
stack<int> stk;
stk.push(0); cnt[0] = 0;
for (int i = 1; i <= n; i ++ ) {
cnt[i] = cnt[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
if (cnt[i] < cnt[stk.top()]) stk.push(i);
}
for (int i = n; i > 0; i -- ) {
while (!stk.empty() && cnt[i] > cnt[stk.top()]) {
ans = max(ans, i - stk.top());
stk.pop();
}
}
return ans;
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间复杂度：\(O(n)\)。