本题可以一步步优化,故很容易作为面试考题被面试官步步拷打
解法一
劳累天数大于不劳累天数 等价于 劳累天数减去不劳累天数大于0
,那么把劳累的一天视作 nums[i]=1
,不劳累的一天视作 nums[i]=−1
,则问题变为:计算 nums
的最长子数组,其元素和大于 0。
既然提到了子数组的元素和,那么自然可以想到使用前缀和来优化。那么问题就变成了:固定区间右端点r,求出最靠左的左端点使得区间[l + 1, r]
,满足 $S[r] - S[l] > 0$
假设在i
的左边有两个点j
和k
都满足s[j] < s[i]
和 s[k] < s[i]
且满足k > j,s[k] > s[j]
,那么k
一定不会使区间的最靠左的左端点,因为j
一定比k
更优,因此只有当s[k] < s[j]
时我们才会将当前的s[k]
入栈。
这样处理之后的栈中维护的就是一个严格单调递减序列的下标,因此我们要找出小于s[i]
的最小的数j
,就可以用二分来求了,避免每次遍历stk的所有元素,时间复杂度由$O(n^2)$优化为$O(nlogn)$
由于本题的特殊性 [本题中前缀和是连续的,相邻两个数的前缀和之间只差1
],因此还可以进一步优化。
要找到小于s[i]
的最小的数,找完s[i]
再找s[i+1]
时,二者之间一定差1
,假设我们已经找到了满足条件s[j] < s[i]
的最小的j
,那么求后面小于s[i+1]
的最小的数时,如果s[i+1] = s[i] + 1
,那么要找到数一定为j
或者j-1
,因为j
是最小的满足s[j] < s[i]
的数,那么一定有s[j-1] >= s[i]
,因为s[j-2] >= s[j-1] + 1
,即s[j-2] >= s[i] + 1 = s[i+1]
,所以一定不会取到j-2
同理,如果s[i+1] = s[i] - 1
,那么要找的数一定为j
或者j+1
,因为s[j] < s[i]
成立,但是s[j] < s[i+1]
是不一定成立的,如果成立,那么自然j
就是满足s[j] < s[i+1]
的最小的数,如果不成立,因为s[j+1] <= s[j] - 1
,所以s[j+1] < s[i] - 1 = s[i+1]
一定成立,那么j+1
自然就是满足条件的最小的数了。
前缀和 + 单调栈 + 二分
注:虽然下面的代码没有用到
stack
,但用pos
存储的是一个单调递减序列的下标,与单调栈的思想无异,只是因为栈不支持索引故改为vector
class Solution {
public:
int longestWPI(vector<int>& hours) {
int n = hours.size();
vector<int> S(n + 1);
vector<int> pos;
pos.push_back(0);
for (int i = 1; i <= n; i++) {
S[i] = S[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
// 当前元素必须小于当前栈顶元素 才可以入栈 入栈的是下标
if (S[i] < S[pos.back()]) pos.push_back(i);
}
int res = 0;
for (int i = 1; i <= n; i++) {
// 二分找到S中小于S[i]的最小的j 即找到第一个小于S[i]的j
int l = 0, r = pos.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (S[pos[mid]] < S[i]) r = mid;
else l = mid + 1;
}
if (S[pos[r]] < S[i]) res = max(res, i - pos[r]);
}
return res;
}
};
前缀和 + 单调栈 + 线性优化写法
class Solution {
public:
int longestWPI(vector<int>& hours) {
int n = hours.size();
vector<int> S(n + 1);
stack<int> stk;// 栈中元素为 s[0]∼s[r−1] 的递减项
stk.push(0); // 下标为0 且S[0]=0,所以下面stk中存储的下标对应的前缀和都是小于0的
for (int i = 1; i <= n; i++) {
S[i] = S[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
// 当前元素必须小于当前栈顶元素 才可以入栈 入栈的是下标
if (S[i] < S[stk.top()]) stk.push(i); //
}
int res = 0;
for (int i = n; i >= 1; i--) {
// 对于栈顶s[j] 考虑比它大的最远的s[i],那么我们从后往前遍历即可 只要 s[i] > s[j]就统计最大值
while (!stk.empty() && S[i] > S[stk.top()]) {
res = max(res, i - stk.top()); // [栈顶,i) 可能是最长子数组
stk.pop();
}
}
return res;
}
};
解法二
前缀和 + 哈希表 + 数学(脑筋急转弯,利用前缀和是连续的,每一项为1或-1)
-
如果前缀和
s[i] > 0
,那么j=0
就是最小的左端点,因为s[j]
一定为0,满足s[i] > s[j]
-
如果前缀和
s[i] <= 0
,那么j
就是s[i] - 1
第一次出现的位置,因为前缀和是从0开始的,且数组的数只有1和-1两种,那么i
前面的小于s[i]
的数一定会有s[i]-1
,因此,第一个s[i]-1
出现的位置就是区间的左端点。
为什么是
s[i] - 1
而不是s[i] - 2
或者其他的呢?因为要考虑到本题的连续性,小于
s[i]
的第一个出现的数就是s[i]-1
了,且此时满足s[i] <= 0
,从0
得到s[i]
的过程一定会最先得到s[i] - 1
,然后才会有s[i] - 2
等等。
class Solution {
public:
int longestWPI(vector<int>& hours) {
unordered_map<int, int> mp;
int n = hours.size();
int res = 0, sum = 0;
// 将大于8的分数记为+1 小于8的记为-1
for (int i = 0; i < n; i++) {
if (hours[i] > 8) sum++;
else sum--;
if (sum > 0) res = i + 1; // 如果 sum > 0 那么最靠左的左端点一定为0 满足Si - Sj > 0
else {
// sum < 0,那么最靠左的满足Si - Sj > 0 的 Sj 一定为 Si - 1(画图,S从0开始变到Sj)
if (mp.count(sum - 1)) res = max(res, i - mp[sum - 1]); // 区间为[j+1, i]
if (!mp.count(sum)) mp[sum] = i;
}
}
return res;
}
};
- 图片参考:灵茶山艾府