給你一份工作時(shí)間表 hours恭朗，上面記錄著某一位員工每天的工作小時(shí)數(shù)初厚。
我們認(rèn)為當(dāng)員工一天中的工作小時(shí)數(shù)大于 8 小時(shí)的時(shí)候被啼，那么這一天就是「勞累的一天」曾撤。
所謂「表現(xiàn)良好的時(shí)間段」斩披，意味在這段時(shí)間內(nèi)溜族，「勞累的天數(shù)」是嚴(yán)格 大于「不勞累的天數(shù)」。
請(qǐng)你返回「表現(xiàn)良好時(shí)間段」的最大長(zhǎng)度垦沉。
示例 1：
輸入：hours = [9, 9, 6, 0, 6, 6, 9]
輸出：3
解釋：最長(zhǎng)的表現(xiàn)良好時(shí)間段是 [9,9,6]煌抒。
這個(gè)思路是看的解題思路里面一個(gè)Python3大佬的答案寫的。
https://leetcode-cn.com/problems/longest-well-performing-interval/solution/
大佬就是大佬厕倍，即使給出了思路寡壮，我還是看了好久好久才看懂，期間還去補(bǔ)習(xí)了單調(diào)棧和前綴和的知識(shí)才看懂思路讹弯。
不了解或者不夠熟悉推薦再去補(bǔ)一下相關(guān)知識(shí)：
單調(diào)棧和應(yīng)用實(shí)踐
前綴和
首先根據(jù)時(shí)間是否大于8况既，量化成1和-1利與計(jì)算， [9, 9, 6, 0, 6, 6, 9] => [1, 1, -1, -1, -1, -1, 1]闸婴，所以hours當(dāng)前是[1, 1, -1, -1, -1, -1, 1]坏挠。
這個(gè)操作比較好理解，其實(shí)理解題意邪乍，我們要做的就是得到一個(gè)區(qū)間降狠，這個(gè)區(qū)間里1和-1加起來要大于0。怎么方便的得到一個(gè)區(qū)間的和庇楞？很明顯榜配，這就是前綴和存在的意義。
轉(zhuǎn)化成前綴和prefixSrc = [0, 1, 2, 1, 0, -1, -2, -1]吕晌，我們?cè)谇熬Y和前面加了一個(gè)0蛋褥，是為了好操作。那如何得到一個(gè)區(qū)間呢睛驳？如果要得到[1,3]區(qū)間,根據(jù)前綴和定義需要用prefixSrc[3]-prefixSrc[1]烙心，所以我們需要得到數(shù)組中所有prefixSrc[b]-prefixSrc[a] > 0的[a,b]區(qū)間，就是我們需要的結(jié)果乏沸。
上圖所示淫茵，我們需要的就是那兩段紅色線段。我們選擇從后往前遍歷蹬跃，
如何得到第二段紅色線段呢匙瘪？
index=7，prefixSrc[7]=-1;需要找到左邊第一個(gè)比自己小的數(shù)字。這段描述熟悉不丹喻？到了單調(diào)棧登場(chǎng)的時(shí)候了薄货。
我們對(duì)prefixSrc = [0, 1, 2, 1, 0, -1, -2, -1]生成單調(diào)棧，stack=[0,5,6]碍论，對(duì)應(yīng)[0, -1, -2]谅猾，如果當(dāng)前元素大于棧頂元素，棧頂元素出棧鳍悠，因?yàn)?1 > -2赊瞬，所以6出棧，計(jì)算寬度width=7-6=1贼涩。
如何得到第一段紅色線段呢巧涧？
其實(shí)因?yàn)槲覀儽憷絠ndex=3的時(shí)候prefixSrc[3]的時(shí)候發(fā)現(xiàn)prefixSrc[3]大于0，此時(shí)棧內(nèi)只剩一個(gè)0遥倦，所以寬度width=3-0=3
因?yàn)?永遠(yuǎn)在第0位所以只要出現(xiàn)大于0的情況谤绳，0~n就是表現(xiàn)良好時(shí)間段成立的。
我們繼續(xù)舉個(gè)例子：
OA段跟BCD段都是我們需要的袒哥，而AB段則不是缩筛。想明白這個(gè)就明白了。
- DCB:從D往C遍歷的過程中我們會(huì)不斷把單調(diào)棧里面的index彈出去堡称，直到B瞎抛，得到DCB的寬度。
- AO:到A后發(fā)現(xiàn)大于零却紧，彈出棧底的0桐臊，得到OA的寬度
代碼實(shí)現(xiàn)：
/**
* 使用前綴和+單調(diào)棧
*
* @param src 源數(shù)組
*/
public int longestWPI(int[] hours) {
int max = 0;
Stack<Integer> stack = new Stack<>();
int[] prefixSrc = new int[hours.length + 1];
//大于8的置為1，否則置為-1
for (int i = 0; i < hours.length; i++) {
if (hours[i] > 8) {
max = 1;
hours[i] = 1;
} else {
hours[i] = -1;
}
//初始化前綴和數(shù)組
prefixSrc[0] = 0;
prefixSrc[i + 1] = prefixSrc[i] + hours[i];
}
for (int i = 0; i < prefixSrc.length - 1; i++) {
//實(shí)現(xiàn)單調(diào)棧
if (stack.isEmpty()) {
stack.push(i);
} else {
if (prefixSrc[i] < prefixSrc[stack.peek()]) {
stack.push(i);
}
}
}
//開始尋找,從后往前遍歷
for (int i = prefixSrc.length - 1; i >= 0; i--) {
int last = i;
while (!stack.isEmpty() && prefixSrc[i] > prefixSrc[stack.peek()]) {
last = stack.pop();
}
if (last != i) {
int width = i - last;
max = max > width ? max : width;
}
}
return max;
}
