表現(xiàn)良好的最長時間段【LC1124】

給你一份工作時間表 hours，上面記錄著某一位員工每天的工作小時數(shù)。

我們認為當員工一天中的工作小時數(shù)大于 8 小時的時候，那么這一天就是「勞累的一天」。

所謂「表現(xiàn)良好的時間段」，意味在這段時間內(nèi)，「勞累的天數(shù)」是嚴格 大于「不勞累的天數(shù)」。

請你返回「表現(xiàn)良好時間段」的最大長度。

下文為自己的題解總結(jié)，參考其他題解寫成，取其精華，做以筆記，如有描述不清楚或者錯誤麻煩指正，不勝感激，不喜勿噴！
2023/2/14
看了提示還是只能雙層循環(huán) 哎…

• 思路：

  • 首先構造新的數(shù)組及其前綴和數(shù)組，新數(shù)組中將工作時長大于8的記為1，工作時長小于等于8的記為-1，并求出它的前綴和數(shù)組，那么題意可以轉(zhuǎn)化為$?$和嚴格大于0的連續(xù)子數(shù)組的最大長度$?$
  • 那么可以通過三種方法求出$?$和嚴格大于0的連續(xù)子數(shù)組的最大長度$?$
    • 暴力
    • 哈希表
    • 單調(diào)棧

• 實現(xiàn)：暴力

  class Solution {public int longestWPI(int[] hours) {int n = hours.length;int[] preSum = new int[n + 1];int res = 0;for (int i = 0; i < n; i++){            preSum[i + 1] = hours[i] > 8 ? preSum[i] + 1 : preSum[i] - 1;          }for (int i = 0; i < n; i++){for (int j = i + 1; j <= n; j++){if (preSum[j] - preSum[i] > 0){res = Math.max(res, j - i);}}}return res;}
  }
  

  • 復雜度

    • 時間復雜度：$O(n^2)$
    • 空間復雜度：$O(n)$

• 實現(xiàn)：哈希表

  • 由于新數(shù)組中的值只存在1和-1，因此相鄰前綴和的差恰好為1
  • 利用前綴和數(shù)組的性質(zhì)可得
    • 當$preSum[i]>0$時，最遠的左端點即為$j=0$
    • 當$preSum[i]<=0$時，最遠的左端點即為$j$為$preSum[i]?1$首次出現(xiàn)的位置
  • 實現(xiàn)時，使用變量代替前綴和數(shù)組

  class Solution {public int longestWPI(int[] hours) {int n = hours.length;int preSum = 0;Map<Integer, Integer> map = new HashMap<>();int res = 0;for (int i = 0; i < n; i++){            preSum += hours[i] > 8 ? 1 : -1; if (preSum > 0){res = Math.max(res, i + 1);}else if (map.containsKey(preSum - 1)){res = Math.max(i - map.get(preSum - 1), res);}if (!map.containsKey(preSum)){map.put(preSum, i);}}return res;}
  }
  

  class Solution {public int longestWPI(int[] hours) {int n = hours.length, ans = 0, s = 0;var pos = new int[n + 2]; // 記錄前綴和首次出現(xiàn)的位置for (int i = 1; i <= n; ++i) {s -= hours[i - 1] > 8 ? 1 : -1; // 取反，改為減法if (s < 0) ans = i;else {if (pos[s + 1] > 0) ans = Math.max(ans, i - pos[s + 1]);if (pos[s] == 0) pos[s] = i;}}return ans;}
  }作者：靈茶山艾府
  鏈接：https://leetcode.cn/problems/longest-well-performing-interval/solutions/2110211/liang-chong-zuo-fa-liang-zhang-tu-miao-d-hysl/
  來源：力扣（LeetCode）
  著作權歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權，非商業(yè)轉(zhuǎn)載請注明出處。
  

  • 復雜度
    • 時間復雜度：$O(n)$
    • 空間復雜度：$O(n)$

• 實現(xiàn)：單調(diào)棧

  • 當$s[j]<s[i]$時，$j$可以作為左端點，而我們要求最大長度，因此應該盡可能讓$j$位于左端點，因此可以使用單調(diào)遞減棧存放preSum中遞減元素的下標
  • 而如果存在$s[r_1]<s[r_2],r_1<r_2$的情況時，$r_1$一定不是最遠的右端點，因為存在一個左端點滿足$s[l]<s[r_1]<s[r_2],l<r_1<r_2$，那么此時最長子數(shù)組區(qū)間為$[l,r_2]$，因此為了避免再次將元素放入棧中，我們可以選擇倒序遍歷右端點

  class Solution {public int longestWPI(int[] hours) {int n = hours.length, ans = 0;var s = new int[n + 1]; // 前綴和var st = new ArrayDeque<Integer>();st.push(0); // s[0]for (int j = 1; j <= n; ++j) {s[j] = s[j - 1] + (hours[j - 1] > 8 ? 1 : -1);if (s[j] < s[st.peek()]) st.push(j); // 感興趣的 j}for (int i = n; i > 0; --i)while (!st.isEmpty() && s[i] > s[st.peek()])ans = Math.max(ans, i - st.pop()); // [棧頂,i) 可能是最長子數(shù)組return ans;}
  }作者：靈茶山艾府
  鏈接：https://leetcode.cn/problems/longest-well-performing-interval/solutions/2110211/liang-chong-zuo-fa-liang-zhang-tu-miao-d-hysl/
  來源：力扣（LeetCode）
  著作權歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權，非商業(yè)轉(zhuǎn)載請注明出處。
  

  • 復雜度
    • 時間復雜度：$O(n)$
    • 空間復雜度：$O(n)$