给你一份销售数量表 sales,上面记录着某一位销售员每天成功推销的产品数目。
我们认为当销售员同一天推销的产品数目大于 8 个的时候,那么这一天就是「成功销售的一天」。
所谓「销售出色区间」,意味在这段时间内,「成功销售的天数」是严格 大于「未成功销售的天数」。
请你返回「销售出色区间」的最大长度。
示例 1:
输入:sales = [10,2,1,4,3,9,6,9,9]
输出:5
解释:最大销售出色区间是 [3,9,6,9,9]。
示例 2:
输入:sales = [5,6,7]
输出:0
提示:
1 <= sales.length <= 104
0 <= sales[i] <= 16
class Solution {
public:
int longestESR(vector<int>& sales) {
int n = sales.size();
// 求前缀和
vector<int> f(n + 1);
for (int i = 1; i <= n; i++) f[i] = f[i - 1] + (sales[i - 1] > 8 ? 1 : -1);
// 把下标按前缀和的值分类
map<int, vector<int>> mp;
for (int i = 0; i <= n; i++) mp[f[i]].push_back(i);
// mn 是 f[i] 小于当前前缀和的最小的 i
int ans = 0, mn = 1e9;
// 从小到大枚举前缀和
for (auto it = mp.begin(); it != mp.end(); it++) {
// 更新答案
for (int x : (it->second)) ans = max(ans, x - mn);
// 更新 mn
for (int x : (it->second)) mn = min(mn, x);
}
return ans;
}
};