单调栈

//单调栈
class monotonicStack {
public:
	monotonicStack(int type, bool force) { //0递减栈，栈顶最小，1递增栈，栈顶最大, force表示是否是强制单调栈
		this->type = type, this ->force = force;
	}
	void push(int x) {
		if (force) {
			while (!s.empty() && (type ? (s.top() > x) : (s.top() < x)))s.pop();
			s.push(x);
		}
		else {
			if (s.empty() || (type ? (s.top() <= x) : (s.top() >= x)))s.push(x);
		}
	}
	void pop() {
		if (!s.empty())s.pop();
	}
	int top() {
		return s.top();
	}
private:
	stack<int>s;
	int type;
	bool force;
};

二，数组大小关系计算

利用强制入栈单调栈，实现线性时间内计算vector每个数前面最近的满足指定的序关系的数的ID。

class SingleVectorOpt
{
public:
	//翻转vector、翻转二维vector的每一行
	template<typename T>
	static vector<T> frev(const vector<T>& v)
	{
		vector<T> ans;
		ans.resize(v.size());
		for (int i = 0; i < v.size(); i++)ans[i] = v[v.size() - 1 - i];
		return ans;
	}
	template<typename T>
	static vector<vector<T>> frev(const vector<vector<T>>& v)
	{
		vector<vector<T>>ans;
		for (int i = 0; i < v.size(); i++)ans.push_back(frev(v[i]));
		return ans;
	}
	//vector乘一个数
	template<typename T1, typename T2>
	static void fcheng(vector<T1>& v, T2 n)
	{
		for (int i = v.size() - 1; i >= 0; i--)v[i] *= n;
	}
	//vector加一个数
	template<typename T1, typename T2>
	static void fjia(vector<T1>& v, T2 n)
	{
		for (int i = v.size() - 1; i >= 0; i--)v[i] += n;
	}
	//返回vector每个数前面最近的满足pr关系的数的ID,-1 或者 0到size-1
	template<typename T, class P>
	static inline vector<int>firstInLeft(vector<T>v, P pr)
	{
		vector<int> ans;
		if (v.size() == 0)return ans;
		stack<T>st;
		st.push(0);
		ans.push_back(-1);
		for (int i = 1; i < v.size(); i++) //代码用单调栈实现，时间复杂度为O（n）
		{
			while (!st.empty() && !pr(v[st.top()], v[i]))st.pop();
			if (st.empty())ans.push_back(-1);
			else ans.push_back(st.top());
			st.push(i);
		}
		return ans;
	}

	//返回vector每个数前面最近的比它小的数的ID,-1 或者 0到size-1
	template<typename T>
	static vector<int> fminlef(vector<T> v)
	{
		return firstInLeft(v, [](T a, T b) {return a < b; });  //可换为自定义函数
	}
	//返回vector每个数前面最近的比它小或等于的数的ID,-1 或者 0到size-1
	template<typename T>
	static vector<int> fminlef2(vector<T> v)
	{
		return firstInLeft(v, [](T a, T b) {return a <= b; });  //可换为自定义函数
	}
	//返回vector每个数前面最近的比它大的数的ID,-1 或者 0到size-1
	template<typename T>
	static vector<int> fmaxlef(vector<T> v)
	{
		fcheng(v, -1);
		vector<int>ans = fminlef(v);
		return ans;
	}
	//返回vector每个数前面最近的比它大或等于的数的ID,-1 或者 0到size-1
	template<typename T>
	static vector<int> fmaxlef2(vector<T> v)
	{
		fcheng(v, -1);
		vector<int>ans = fminlef2(v);
		return ans;
	}

	//返回vector每个数后面最近的比它小的数的ID,size 或者 0到size-1
	template<typename T>
	static vector<int> fminrig(vector<T> v)
	{
		vector<int>v1 = frev(v), v2 = fminlef(v1);
		fcheng(v2, -1);
		fjia(v2, v.size() - 1);
		return frev(v2);
	}
	//返回vector每个数后面最近的比它小或等于的数的ID,size 或者 0到size-1
	template<typename T>
	static vector<int> fminrig2(vector<T> v)
	{
		vector<int>v1 = frev(v), v2 = fminlef2(v1);
		fcheng(v2, -1);
		fjia(v2, v.size() - 1);
		return frev(v2);
	}
	//返回vector每个数后面最近的比它大的数的ID,size 或者 0到size-1
	template<typename T>
	static vector<int> fmaxrig(vector<T> v)
	{
		vector<int>v1 = frev(v), v2 = fmaxlef(v1);
		fcheng(v2, -1);
		fjia(v2, v.size() - 1);
		return frev(v2);
	}
	//返回vector每个数后面最近的比它大或等于的数的ID,size 或者 0到size-1
	template<typename T>
	static vector<int> fmaxrig2(vector<T> v)
	{
		vector<int>v1 = frev(v), v2 = fmaxlef2(v1);
		fcheng(v2, -1);
		fjia(v2, v.size() - 1);
		return frev(v2);
	}
};

这里面的firstInLeft函数就是用单调栈实现的，并且我做了封装，所以很多OJ题目原本要手写单调栈，有了我的模板就可以直接用了。

力扣 739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        auto v=Fmaxrig(temperatures);
        for(int i=0;i<v.size();i++){
            if(v[i]==v.size())v[i]=0;
            else v[i]-=i;
        }
        return v;
    }
};

力扣 907. 子数组的最小值之和

给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。

由于答案可能很大，因此返回答案模 10^9 + 7。

示例：

输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

提示：

1 <= A <= 30000
1 <= A[i] <= 30000


 
class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        vector<int>v1=fminlef(A),v2=fminrig2(A);
        int ans=0;
        for(int i=0;i<A.size();i++)
        {
            int m=min(i-v1[i],v2[i]-i);
            ans+=(v2[i]-v1[i]-m)*m*A[i],ans%=1000000007;
        }
        return ans;
    }
};

力扣 84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：

输入： heights = [2,4]
输出： 4

提示：

1 <= heights.length <=105
0 <= heights[i] <= 104

class Solution {
public:
	int largestRectangleArea(vector<int>& heights) {
		vector<int> id = Fminlef(heights),id2 = Fminrig(heights);
		int ans = 0;
		for (int i = 0; i < heights.size(); i++) {
			ans = max(ans, (id2[i] - id[i]-1) * heights[i]);
		}
		return ans;
	}
};

力扣 85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = [["0"]]
输出：0

示例 3：

输入：matrix = [["1"]]
输出：1

提示：

rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        vector<int>heights(matrix[0].size(),0);
        int ans=0;
        for(auto v:matrix){
            for(int i=0;i<v.size();i++){
                if(v[i]=='0')heights[i]=0;
                else heights[i]++;
            }
            ans=max(ans,largestRectangleArea(heights));
        }
        return ans;
    }
    int largestRectangleArea(vector<int>& heights) {
		vector<int> id = Fminlef(heights),id2 = Fminrig(heights);
		int ans = 0;
		for (int i = 0; i < heights.size(); i++) {
			ans = max(ans, (id2[i] - id[i]-1) * heights[i]);
		}
		return ans;
	}
};

力扣 2454. 下一个更大元素 IV

给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。

如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：

j > i
nums[j] > nums[i]
恰好存在一个 k 满足 i < k < j 且 nums[k] > nums[i] 。

如果不存在 nums[j] ，那么第二大整数为 -1 。

比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。

请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。

示例 1：

输入：nums = [2,4,0,9,6]
输出：[9,6,6,-1,-1]
解释：
下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。

示例 2：

输入：nums = [3,3]
输出：[-1,-1]
解释：
由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109

class Solution {
public:
	vector<int> secondGreaterElement(vector<int>& nums) {
		auto ids = SingleVectorOpt::fmaxrig(nums);
		vector<int>ans(nums.size(), -1);
		unordered_map<int, int>dp;
		for (int i = 0; i < nums.size(); i++) {
			int id = ids[i] + 1;
			if (id < dp[nums[i]])id = dp[nums[i]];
			if (dp[nums[i]] == 0)dp[nums[i]] = nums.size();
			while (id < nums.size()) {
				if (nums[id] > nums[i]) {
					ans[i] = nums[id];
					dp[nums[i]] = id;
					break;
				}
				id = ids[id];
			}
		}
		return ans;
	}
};

力扣 2865. 美丽塔 I

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是美丽的：

1 <= heights[i] <= maxHeights[i]
heights 是一个山状数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个山状数组：

对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]

请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

示例 1：

输入：maxHeights = [5,3,4,1,1]
输出：13
解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]  
- heights 是个山状数组，峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。

示例 2：

输入：maxHeights = [6,5,3,9,2,7]
输出：22
解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组，峰值在 i = 3 处。
22 是所有美丽塔方案中的最大高度和。

示例 3：

输入：maxHeights = [3,2,5,5,2,3]
输出：18
解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组，最大值在 i = 2 处。
注意，在这个方案中，i = 3 也是一个峰值。
18 是所有美丽塔方案中的最大高度和。

提示：

1 <= n == maxHeights <= 103
1 <= maxHeights[i] <= 109

class Solution {
public:
	long long maximumSumOfHeights(vector<int>& maxHeights) {
		auto v1 = Fminlef(maxHeights);
		auto v2 = Fminrig(maxHeights);
		vector<long long>ans1(v1.size());
		vector<long long>ans2(v2.size());
		for (long long i = 0; i < v1.size(); i++) {
			if (v1[i] >= 0)ans1[i] = ans1[v1[i]] + (i - v1[i])*maxHeights[i];
			else ans1[i] = (i + 1)*maxHeights[i];
		}
		for (long long i = v2.size() - 1; i >= 0; i--) {
			if (v2[i] < v2.size())ans2[i] = ans2[v2[i]] + (v2[i] - i)*maxHeights[i];
			else ans2[i] = (v2.size() - i)*maxHeights[i];
		}
		long long ans = 0;
		for (int i = 0; i < v1.size(); i++)ans = max(ans, ans1[i] + ans2[i] - maxHeights[i]);
		return ans;
	}
};

力扣 2866. 美丽塔 II

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是美丽的：

1 <= heights[i] <= maxHeights[i]
heights 是一个山状数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个山状数组：

对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]

请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

示例 1：

输入：maxHeights = [5,3,4,1,1]
输出：13
解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]  
- heights 是个山状数组，峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。

示例 2：

输入：maxHeights = [6,5,3,9,2,7]
输出：22
解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组，峰值在 i = 3 处。
22 是所有美丽塔方案中的最大高度和。

示例 3：

输入：maxHeights = [3,2,5,5,2,3]
输出：18
解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组，最大值在 i = 2 处。
注意，在这个方案中，i = 3 也是一个峰值。
18 是所有美丽塔方案中的最大高度和。

提示：

1 <= n == maxHeights <= 105
1 <= maxHeights[i] <= 109

class Solution {
public:
	long long maximumSumOfHeights(vector<int>& maxHeights) {
		auto v1 = Fminlef(maxHeights);
		auto v2 = Fminrig(maxHeights);
		vector<long long>ans1(v1.size());
		vector<long long>ans2(v2.size());
		for (long long i = 0; i < v1.size(); i++) {
			if (v1[i] >= 0)ans1[i] = ans1[v1[i]] + (i - v1[i])*maxHeights[i];
			else ans1[i] = (i + 1)*maxHeights[i];
		}
		for (long long i = v2.size() - 1; i >= 0; i--) {
			if (v2[i] < v2.size())ans2[i] = ans2[v2[i]] + (v2[i] - i)*maxHeights[i];
			else ans2[i] = (v2.size() - i)*maxHeights[i];
		}
		long long ans = 0;
		for (int i = 0; i < v1.size(); i++)ans = max(ans, ans1[i] + ans2[i] - maxHeights[i]);
		return ans;
	}
};

力扣 1944. 队列中可以看到的人数

有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。

一个人能看到他右边另一个人的条件是这两人之间的所有人都比他们两人矮。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。

请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能看到的人数。

示例 1：

输入：heights = [10,6,8,5,11,9]
输出：[3,1,2,1,1,0]
解释：
第 0 个人能看到编号为 1 ，2 和 4 的人。
第 1 个人能看到编号为 2 的人。
第 2 个人能看到编号为 3 和 4 的人。
第 3 个人能看到编号为 4 的人。
第 4 个人能看到编号为 5 的人。
第 5 个人谁也看不到因为他右边没人。

示例 2：

输入：heights = [5,1,2,3,10]
输出：[4,1,1,1,0]

提示：

n == heights.length
1 <= n <= 105
1 <= heights[i] <= 105
heights 中所有数 互不相同 。

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        vector<int>v1=Fmaxlef(heights);
        vector<int>v2=Fmaxrig(heights);
        vector<int>ans(heights.size());
        for(int i=0;i<ans.size();i++)ans[i]=(v2[i]<ans.size());
        for(auto x:v1){
            if(x!=-1)ans[x]++;
        }
        return ans;
    }
};

三，其他实战

力扣 155. 最小栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.

提示：

各函数的调用总次数不超过 20000 次

class MinStack {
public:
    stack<int>s;//主栈
    stack<int>m;//单调栈
 
    MinStack() {
    }
    
    void push(int x) {
        s.push(x);
        if(m.empty()||m.top()>=x)m.push(x);
    }
    
    void pop() {
        if(m.top()==s.top())m.pop();
        s.pop();        
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return m.top();
    }
};

力扣面试题 03.02. 栈的最小值

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

题目和力扣 155. 最小栈一模一样，就是接口名称变了。

代码：

略。

力扣 716. 最大栈

设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。

实现 MaxStack 类：

MaxStack() 初始化栈对象
void push(int x) 将元素 x 压入栈中。
int pop() 移除栈顶元素并返回这个元素。
int top() 返回栈顶元素，无需移除。
int peekMax() 检索并返回栈中最大元素，无需移除。
int popMax() 检索并返回栈中最大元素，并将其移除。如果有多个最大元素，只要移除 最靠近栈顶 的那个。

示例：

输入
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
输出
[null, null, null, null, 5, 5, 1, 5, 1, 5]

解释
MaxStack stk = new MaxStack();
stk.push(5);   // [5] - 5 既是栈顶元素，也是最大元素
stk.push(1);   // [5, 1] - 栈顶元素是 1，最大元素是 5
stk.push(5);   // [5, 1, 5] - 5 既是栈顶元素，也是最大元素
stk.top();     // 返回 5，[5, 1, 5] - 栈没有改变
stk.popMax();  // 返回 5，[5, 1] - 栈发生改变，栈顶元素不再是最大元素
stk.top();     // 返回 1，[5, 1] - 栈没有改变
stk.peekMax(); // 返回 5，[5, 1] - 栈没有改变
stk.pop();     // 返回 1，[5] - 此操作后，5 既是栈顶元素，也是最大元素
stk.top();     // 返回 5，[5] - 栈没有改变

提示：

-107 <= x <= 107
最多调用 104 次 push、pop、top、peekMax 和 popMax
调用 pop、top、peekMax 或 popMax 时，栈中 至少存在一个元素

进阶：

试着设计解决方案：调用 top 方法的时间复杂度为 O(1) ，调用其他方法的时间复杂度为 O(logn) 。

思路一：单调栈

class MaxStack {
public:
	MaxStack() {
		v.clear();
	}
 
	void push(int x) {
		v.push_back(x);
		if (sd.empty() || v[sd.top()] <= x)sd.push(v.size() - 1);
	}
 
	int pop() {
		int t = top();
		v.erase(v.end() - 1);
		if (!sd.empty() && v.size() - 1 < sd.top())sd.pop();
		return t;
	}
 
	int top() {
		return v.back();
	}
 
	int peekMax() {
		return v[sd.top()];
	}
 
	int popMax() {
		int t = sd.top();
		int ans = v[t];
		v.erase(v.begin() + t);
		sd.pop();
		for (int i = t; i < v.size(); i++)if (sd.empty() || v[sd.top()] <= v[i])sd.push(i);
		return ans;
	}
	vector<int>v;
	stack<int>sd;//id形式的单调栈
};

时间复杂度不达标，但是之前也AC了，后来力扣扩充了测试集，又不行了。

思路二：用2个map分别存现存数据和删除数据，对数据主体做懒惰删除处理。

#define DelEnd(x) x.erase(--(x.end()))
class MaxStack {
public:
	MaxStack() {
	}

	int top() {
		while (true) {
			int t = v.back();
			if (m2[t].empty())break;
			if (!m[t].empty()&& *(m[t].rbegin())> *(m2[t].rbegin()))break;
			DelEnd(m2[t]);
			DelEnd(v);
		}
		return v.back();
	}

	void push(int t) {
		v.push_back(t);
		int num = 0;
		if (!m[t].empty())num = max(num, *(m[t].rbegin()));
		if (!m2[t].empty())num = max(num, *(m2[t].rbegin()));
		m[t].insert(num + 1);
	}

	int pop() {
		int t = top();
		DelEnd(m[t]);
		DelEnd(v);
		return t;
	}

	int peekMax() {
		while (m.rbegin()->second.empty())DelEnd(m);
		return m.rbegin()->first;
	}

	int popMax() {
		int t = peekMax();
		m2[t].insert(*(m[t].rbegin()));
		DelEnd(m[t]);
		return t;
	}
	map<int, set<int>>m;//现存列表
	map<int, set<int>>m2;//删除列表
	vector<int>v;
};

力扣 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 <= 104
0 <= hours[i] <= 16

class Solution:public Bsearch<int> {
public:
	int longestWPI(vector<int>& v) {
		for (int i = 0; i < v.size(); i++) {
			if (v[i] > 8)v[i] = 1;
			else v[i] = -1;
			if (i)v[i] += v[i - 1];
		}
		v.insert(v.begin(), 0);
		int ans = 0;
		map<int, int>m;
		for (int i = 0; i < v.size(); i++) {
			if (vec.empty() || *vec.rbegin() > v[i])vec.push_back(v[i]), m[v[i]] = i;
			target = v[i];
			int id = find(0, vec.size() - 1);
			if(id< vec.size())ans = max(ans, i - m[vec[id]]);
		}
		return ans;
	}
private:
	virtual bool isOk(int x) const //若isOk(x)且!isOk(y)则必有y<x
	{
		return vec[x] < target;
	}
private:
	vector<int>vec;
	int target;
};

力扣 901. 股票价格跨度

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的跨度。

当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

StockSpanner() 初始化类对象。
int next(int price) 给出今天的股价 price ，返回该股票当日价格的跨度。

示例：

输入：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出：
[null, 1, 1, 1, 2, 1, 4, 6]

解释：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80);  // 返回 1
stockSpanner.next(60);  // 返回 1
stockSpanner.next(70);  // 返回 2
stockSpanner.next(60);  // 返回 1
stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85);  // 返回 6

提示：

1 <= price <= 105
最多调用 next 方法 104 次

class StockSpanner{
public:
	StockSpanner() {
		while (!s.empty())s.pop();
		m.clear();
	}

	int next(int x) {
		int t = 1;
		while (!s.empty() && (s.top() <= x)) {
			t += m[s.top()];
			s.pop();
		}
		s.push(x);
		return m[x] = t;
	}
	map<int, int>m;
	stack<int>s;
};

力扣 1673. 找出最具竞争力的子序列

给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。

数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。

在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。

示例 1：

输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。

示例 2：

输入：nums = [2,4,3,3,5,4,9,6], k = 4
输出：[2,3,3,4]

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length

class Solution {
public:
	vector<int> mostCompetitive(vector<int>& nums, int k) {
		stack<int>opt;
		vector<int>ans;
		for (int i = 0; i < nums.size(); i++) {
			while (!opt.empty() && opt.top() > nums[i] && opt.size() + nums.size() - i>k)opt.pop();
			opt.push(nums[i]);
		}
		stack<int>s;
		while (!opt.empty()) {
			s.push(opt.top());
			opt.pop();
		}
		while (!s.empty()) {
			ans.push_back(s.top());
			s.pop();
			if (ans.size() == k)return ans;
		}
		return ans;
	}
};