题目
概述：给定一个整数数组，求出这个数组中良好的子数组的最大长度。良好的子数组定义如下：大于8的数的占比超过50%
输入：整数数组，长度范围[1, 10000]，每个数范围[0, 16]
输出：良好的子数组的最大长度
出处：https://leetcode-cn.com/problems/longest-well-performing-interval/
思路
- 参考 刘岳 https://leetcode-cn.com/problems/longest-well-performing-interval/solution/qian-zhui-he-dan-diao-zhan-python3-by-smoon1989/
- 对于本题来说，8是一个分界点，所以小于等于8的数之间没有差别，大于8的数也没有差别，所以可以把小于等于8的数看作-1，大于8的数看作1，那么本题可以转化为求所有元素和大于0的子数组中最长的子数组
- 将数组分解为以索引x为终点的子数组(x属于[0,n-1],设数组长度为n)，先求以索引x为终点的子数组的最优解，然后综合这些最优解可以得到最终答案
- 求以索引x为终点的子数组的解，可以先将数组求前缀和，得到一个前缀和数组，前缀和数组中后一个索引位置的数减去前一个索引位置的数大于0表示一个解，综合所有解可以得到以索引x为终点的子数组的最优解（索引差距最大的）
- 问题的关键在于如何快速找到这个索引差距最大的最优解，可以先找终点x左边最小的数，然后从该最小的数开始，递归地找左边比它大的第一个数，直到无解
- 找左边比它大的第一个数可以用单调栈这一数据结构解决，这里适用的是单调递减栈（构造过程中没有元素弹出，栈为空或当前数小于栈顶元素时，当前数入栈）
- 求解索引x-1为终点的子数组的最优解可以继承求解索引x为终点的子数组的最优解用到的单调栈，因为以被弹出的元素为起点的解以索引x为终点总比以索引x-1为终点更优(长度增加了1)
代码
class Solution {
public int longestWPI(int[] hours) {
int len = hours.length;
int[] preSums = new int[len + 1];
preSums[0] = 0;
for (int i = 1; i <= len; ++i) {
preSums[i] = preSums[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
}
// stack stores index & index starts with 0
LinkedList<Integer> stack = new LinkedList<>();
for (int i = 0; i <= len; ++i) {
if (stack.isEmpty() || preSums[i] < preSums[stack.peek()]) {
stack.push(i);
}
}
// use i > res optimize
int res = 0;
for (int i = len; i > res; --i) {
while (!stack.isEmpty() && preSums[stack.peek()] < preSums[i]) {
res = Math.max(res, i - stack.pop());
}
}
return res;
}
}
