本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
C++单调栈

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

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1：
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。
示例 2：
输入：hours = [6,6,6]
输出：0
提示：
1 <= hours.length <= 10⁴
0 <= hours[i] <= 16

前缀和+单调栈

劳累的一天权值1,不劳累的一天权值-1。某个子数组的权值和大于0,则是表现良好的时间段；否则，不是。子数组[i,j]之和为:preSum[j+1] - preSum[i]。其中i$\in$[0,j]。
如果preSum[i] < preSum[j+1]，则[i,j]是良好表现时段。寻找最大的i。
如果有多个preSum[i]符合，显示取小标最小的。
i1<i2,且preSum[i1] < preSum[i2]，则i1无论如何优于i2，即i1淘汰i2。淘汰后 preSum[stack元素]严格递减。
分两步：
一，预处理建立栈。
二，j从大到小处理栈。两种条件出栈：
a,栈顶元素下标大于当前下标。
b,preSum[栈顶元素] < preSum[j]，[栈顶元素,j]是良好区域。如果是良好时间段，出栈不会影响结果。因为j只会越来越小，即[i,j]的长度也只会越来越小。

代码

核心代码

class Solution {
		public:
			int longestWPI(vector<int>& hours) {
				vector<int> preSum(1);
				for (const auto& n : hours) {
					preSum.emplace_back(preSum.back() + (n > 8 ? 1 : -1));
				}
				stack<int> sta;
				for (int i = 0; i < preSum.size(); i++) {
					if (sta.empty() || (preSum[i] < preSum[sta.top()])) {
						sta.emplace(i);
					}
				}
				int res = 0;
				for (int j = hours.size() - 1; j >= 0; j--) {
					while (sta.size() && (sta.top() > j)) {
						sta.pop();
					}
					while (sta.size() && (preSum[j+1] > preSum[sta.top()])) {
						res = max(res, j + 1 - sta.top());
						sta.pop();
					}
				}
				return res;
			}
		};

单元测试

	vector<int> hours;
		TEST_METHOD(TestMethod11)
		{
			hours = { 9, 9, 6, 0, 6, 6, 9 };
			auto res = Solution().longestWPI(hours);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			hours = { 6,6,6 };
			auto res = Solution().longestWPI(hours);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod13)
		{
			hours = { 9,9,9,9,6,6,6 };
			auto res = Solution().longestWPI(hours);
			AssertEx(7,res);
		}

优化

	while (sta.size() && (sta.top() > j)) {
						sta.pop();
					}

可以被优化掉，() > j ，其长度为负数，自然被排除掉。

class Solution {
		public:
			int longestWPI(vector<int>& hours) {
				vector<int> preSum(1);
				for (const auto& n : hours) {
					preSum.emplace_back(preSum.back() + (n > 8 ? 1 : -1));
				}
				stack<int> sta;
				for (int i = 0; i < preSum.size(); i++) {
					if (sta.empty() || (preSum[i] < preSum[sta.top()])) {
						sta.emplace(i);
					}
				}
				int res = 0;
				for (int j = hours.size() - 1; j >= 0; j--) {	
					while (sta.size() && (preSum[j+1] > preSum[sta.top()])) {
						res = max(res, j + 1 - sta.top());
						sta.pop();
					}
				}
				return res;
			}
		};