力扣1124.表现良好的最长时间段

力扣1124.表现良好的最长时间段

• 单调栈

  • 将所有>8的标为1，所有<=8的标为-1
  • 最终找到一段区间和为>0的区间下标i - j
  • 即最大化i - j (同962.)

•   class Solution {public:int longestWPI(vector<int>& hours) {int n = hours.size() , res = 0,s[n+1];stack<int> st;s[0] = 0;st.push(0);for(int i=1;i<=n;i++){//求前缀和s[i] = s[i-1] + (hours[i - 1] > 8 ? 1 : -1);//顺便找期待的jif(s[i] < s[st.top()]) st.emplace(i);}for(int i = n;i;i--){//找到满足条件的i 计算答案 弹出栈顶while(!st.empty() && s[i] >s[st.top()]){res = max(res,i - st.top());st.pop();}}return res;}};